24 | 动态规划（上）：只需四步，搞定动态规划算法设计

嗯嗯 非常认同老师说的 状态定义是DP最关键的一步，前几天做爬楼梯和零钱兑换题目的时候 就发现同一个状态转移方程，调换了内外循环，就导致结果不一样，后来发现是因为当内外循环变了，状态的含义也就变了。我把这个思考过程记录了下来 http://xuzhougeng.top/archives/difference-between-climb-stairs-and-coin-change-ii#more

#include <stdio.h> int main() { int n, i, j; int s[50][50]; int p[50][50]; scanf("%d", &n); for(i = 1; i <= n; i++) { for(j = 1; j <= i; j++) { scanf("%d", &s[i][j]); } } for(j = 1; j <= n; j++) { p[n][j] = s[n][j]; } for(i = n - 1; i >= 1; i--) { for(j = 1; j <= i; j++) { if(p[i + 1][j] > p[i + 1][j + 1]) { p[i][j] = s[i][j] + p[i + 1][j]; } else { p[i][j] = p[i + 1][j + 1] + s[i][j]; } } } printf("%d\n", p[1][1]); return 0; }

茶艺师学编程 第二种状态定义：从下至上 /*三角形 第二种状态定义：从下之上*/ #include <stdio.h> #define MAX(a, b) ((a) > (b) ? (a) : (b)) int c[21] = {3, 9, 5, 4, 2, 1, 3, 4, 9, 6, 3, 5, 3, 7, 3, 2, 1, 3, 9, 3, 2}; int val[7][7] = {0}; int dpval[7][7] = {0}; int tri(int n){ int a = 0; for (int i = 1; i <= n; i++){ for(int j = 1; j <= i; j++){ val[i][j] = c[a++]; } } for (int i = 1; i <= n; i++){ puts("\t"); for(int j = 1; j <= i; j++){ printf("%d ", val[i][j]); } } } int DPF(int n){ if(n == 6){ dpval[n][1] = {2}; dpval[n][2] = {1}; dpval[n][3] = {3}; dpval[n][4] = {9}; dpval[n][5] = {3}; dpval[n][6] = {2}; } for (int i = n; i > 0; i--){ for (int j = 1; j <= i; j++){ dpval[i][j] = MAX(dpval[i + 1][j], dpval[i + 1][j + 1]) + val[i][j]; } } for (int i = 1; i <= n; i++){ puts("\t"); for(int j = 1; j <= i; j++){ printf("%d ", dpval[i][j]); } } } int end( ){ printf("最大值为%d", dpval[1][1]); } int main( ){ puts("原三角："); tri(6); puts("\n\n（从下之上）处理后的三角；"); DPF(6); puts("\n"); end( ); return 0; }

茶艺师学编程 从上之下 /*三角形 第一种状态定义：从上之下*/ #include <stdio.h> #define MAX(a, b) ((a) > (b) ? (a) : (b)) int c[21] = {3, 9, 5, 4, 2, 1, 3, 4, 9, 6, 3, 5, 3, 7, 3, 2, 1, 3, 9, 3, 2}; int val[7][7] = {0}; int dpval[7][7] = {0}; int tri(int n){ int a = 0; for (int i = 1; i <= n; i++){ for(int j = 1; j <= i; j++){ val[i][j] = c[a++]; } } for (int i = 1; i <= n; i++){ puts("\t"); for(int j = 1; j <= i; j++){ printf("%d ", val[i][j]); } } } int DPF(int n){ if(n == 1){ dpval[n][n] = {3}; } for (int i = 1; i <= n; i++){ for (int j = 1; j <= i; j++){ dpval[i][j] = MAX(dpval[i - 1][j - 1], dpval[i - 1][j]) + val[i][j]; } } for (int i = 1; i <= n; i++){ puts("\t"); for(int j = 1; j <= i; j++){ printf("%d ", dpval[i][j]); } } } int end(int n){ int Mend = 0; for(int i = 1; i <= n; i++){ Mend = MAX(Mend, dpval[n][i]); } printf("最大值为%d", Mend); } int main( ){ puts("原三角："); tri(6); puts("\n\n（从上之下）处理后的三角；"); DPF(6); puts("\n"); end(6); return 0; }

学了递推之后 感觉自己的思维都变懒了，写了递推的方法就不知道循环要怎么写了... #include <stdio.h> #define max(a, b) ((a) > (b) ? (a) : (b)) int tgle [7][7] = { {0}, {0, 3}, {0, 9, 5}, {0, 4, 2, 1}, {0, 3, 4, 9, 6}, {0, 3, 5, 3, 7, 3}, {0, 2, 1, 3, 9, 3, 2}, }; // 递推写法 int dp(int i, int j) { if (i == 0) return tgle[i][j]; return max(dp(i - 1, j - 1), dp(i - 1, j)) + tgle[i][j]; } // 循环写法 int s[50][50] = {0}; int dp1(int i, int j) { if (i == 0) return tgle[i][j]; for (int m = 1; m <= i; m++) { for (int n = 1; n <= 10; n++ ) { s[m][n] = max(s[m - 1][n - 1], s[m - 1][n]) + tgle[m][n]; } } return s[i][j]; } int main() { printf("%d\n", tgle[0][4]); printf("%d, %d\n", dp(2, 2), dp1(2, 2)); return 0; }

茶艺师学编程 两种不一样的状态定义，带来的不仅仅是编写上的不一样，还有的是面对变化的反应难度也不一样。 具体说就是，如果使用第1种从上至下的状态定义，说使用的代码量是比第2种多一点，但是如果这个三角形再增加第7层、第8层，只要把新的数字输进去，这个程序能直接算的。 而第2种，它有一种事后对一个事情盖棺定论的爽快感（说难听点就是事后诸葛亮），就代码量上肯定是比第一种少。但是如果这个三角形再增加第7层、第8层，那这程序就得需要做相应的修改。 一个是保有自身的开放性，能以不变应万变；另一个是虽然处理快，但面对变化就得修改自身。