问题：一个8 * 8矩阵a[8][8]，要求找到一条从a[0][0]到a[7][7]的路径，使得该路径上各点之和值最大，并且规定每个点只能向下走或者向右走。
仔细想一想其实就是个简单的DP问题：
若i > 0 && j > 0 则path_value[i][j] = max{path_value[i - 1][j], path_value[i][j - 1]} + a[i][j]；另外path_value[0][0] = a[0][0]；对i > 0有path_value[i][0] = path_value[i - 1][0] + a[i][0]；对j > 0有path_value[0][j] = path_value[0][j - 1] + a[0][j]。
到此，该问题就迎刃而解了。代码如下：
1 void find_max(int **a, int n, int m, int *res) {
2 if (a == NULL || *a == NULL ||
3 res == NULL || n < 1 || m < 1) {
4 return;
5 }
6
7 int i, j;
8 for (i = 0; i < n; ++i) {
9 if (i == 0) {
10 continue;
11 }
12 *((int *)a + m * i) += *((int *)a + m * (i - 1));
13 }
14 for (i = 0; i < m; ++i) {
15 if (i == 0) {
16 continue;
17 }
18 *((int *)a + i) += *((int *)a + i - 1);
19 }
20 for (i = 1; i < n; ++i) {
21 for (j = 1; j < m; ++j) {
22 *((int *)a + m * i + j) +=
23 MAX(*((int *)a + m * (i - 1) + j), *((int *)a + m * i + j - 1));
24 }
25 }
26 *res = *((int *)a + m * (n - 1) + m - 1);
27 }
这里将传入的二维数组实参转化成指针的指针来传入。
现在假设有个限制k，要求所求得的最大值不能大于k，也就是求路径和最大，且不超过k的值是多少。
这时候我是想不到如何用动态规划算法如何解决了。因为矩阵只有8 * 8，所以可以考虑用暴力dfs来解决，注意回溯即可。代码如下：
1 void find_max_less_than_k(int **a, int n, int m, int x, int y, int k, int *res) {
2 if (a == NULL || *a == NULL ||
3 res == NULL || n < 1 || m < 1 || x < 0 || y < 0) {
4 return;
5 }
6
7 if (x == n - 1 && y == m - 1) {
8 if (*((int *)a + m * x + y) <= k &&
9 *((int *)a + m * x + y) > *res) {
10 *res = *((int *)a + m * x + y);
11 }
12 return;
13 }
14
15 if (x < n - 1) {
16 int resx = 0;
17 int tempx = *((int *)a + m * (x + 1) + y);
18 *((int *)a + m * (x + 1) + y) += *((int *)a + m * x + y);
19 find_max_less_than_k(a, n, m, x + 1, y, k, &resx);
20 if (resx <= k && resx > *res) {
21 *res = resx;
22 }
23 *((int *)a + m * (x + 1) + y) = tempx;
24 }
25
26 if (y < m - 1) {
27 int resy = 0;
28 int tempy = *((int *)a + m * x + y + 1);
29 *((int *)a + m * x + y + 1) += *((int *)a + m * x + y);
30 find_max_less_than_k(a, n, m, x, y + 1, k, &resy);
31 if (resy <= k && resy > *res) {
32 *res = resy;
33 }
34 *((int *)a + m * x + y + 1) = tempy;
35 }
36 }
这题不难，但是写代码要注意细节的处理。
posted on 2012-09-06 14:35
myjfm 阅读(503)
评论(0) 编辑 收藏 引用 所属分类:
算法基础