問題：一個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 閱讀(530)
評論(0) 編輯 收藏 引用 所屬分類:
算法基礎