3.动态规划

有三个限制1.最优子结构性质2.子问题重叠性质3.自底向上的求解方法矩阵连乘积问题可以看到不同的方法化简那么乘的次数也不同动态划归算法#include stdio.h #define NUM 51 int p[NUM]; int m[NUM][NUM]; int s[NUM][NUM]; void MatrixChain(int n) { for (int i 1; i n; i) m[i][i] 0; for (int r 2; r n; r) for (int i 1; i n - r1; i) { int jir-1; m[i][j] m[i1][j] p[i-1]*p[i]*p[j]; s[i][j] i; for (int k i1; k j; k) { int t m[i][k] m[k1][j] p[i-1]*p[k]*p[j]; if (t m[i][j]) { m[i][j] t; s[i][j] k;} } } } void TraceBack(int i, int j) { if(ij) printf(A%d, i); else { printf((); TraceBack(i,s[i][j]); TraceBack(s[i][j]1,j); printf()); } } int main() { int n; scanf(%d, n); int i, temp; for (i0; in; i) scanf(%d%d, p[i], temp); p[n] temp; MatrixChain(n); printf(%d\n, m[1][n]); TraceBack(1, n); return 0; }递归算法#include stdio.h #define NUM 51 int p[NUM]; int m[NUM][NUM]; int s[NUM][NUM]; int Recurve(int i, int j) { if (i j) return 0; int u Recurve(i, i)Recurve(i1,j) p[i-1]*p[i]*p[j]; s[i][j] i; for (int k i1; k j; k) { int t Recurve(i, k) Recurve(k1,j) p[i-1]*p[k]*p[j]; if (t u) { u t; s[i][j] k;} } m[i][j] u; return u; } void TraceBack(int i, int j) { if(ij) printf(A%d, i); else { printf((); TraceBack(i,s[i][j]); TraceBack(s[i][j]1,j); printf()); } } int main() { int n; scanf(%d, n); int i, temp; for (i0; in; i) scanf(%d%d, p[i], temp); p[n] temp; Recurve(1, n); printf(%d\n, m[1][n]); TraceBack(1, n); return 0; }备忘录方法#include stdio.h #include memory.h #define NUM 51 int p[NUM]; int m[NUM][NUM]; int s[NUM][NUM]; int LookupChain(int i, int j) { if (m[i][j]0) return m[i][j]; if (i j) return 0; int u LookupChain(i, i)LookupChain(i1,j) p[i-1]*p[i]*p[j]; s[i][j] i; for (int k i1; k j; k) { int t LookupChain(i, k) LookupChain(k1,j) p[i-1]*p[k]*p[j]; if (t u) { u t; s[i][j] k;} } m[i][j] u; return u; } void TraceBack(int i, int j) { if(ij) printf(A%d, i); else { printf((); TraceBack(i,s[i][j]); TraceBack(s[i][j]1,j); printf()); } } int main() { int n; scanf(%d, n); int i, temp; for (i0; in; i) scanf(%d%d, p[i], temp); p[n] temp; memset(m, 0, sizeof(m)); LookupChain(1, n); printf(%d\n, m[1][n]); TraceBack(1, n); return 0; }最长公共子序列动态规划算法递归算法#include stdio.h #define NUM 100 int c[NUM][NUM]; int b[NUM][NUM]; void LCSLength(int m, int n, const char x[],char y[]) { int i,j; for (i 1; i m; i) c[i][0] 0; for (i 1; i n; i) c[0][i] 0; for (i 1; i m; i) for (j 1; j n; j) { if (x[i]y[j]) {c[i][j]c[i-1][j-1]1; b[i][j]1; } else if (c[i-1][j]c[i][j-1]) {c[i][j]c[i-1][j]; b[i][j]2; } else { c[i][j]c[i][j-1]; b[i][j]3; } } } void LCS(int i,int j,char x[]) { if (i 0 || j0) return; if (b[i][j] 1){ LCS(i-1,j-1,x); printf(%c,x[i]); } else if (b[i][j] 2) LCS(i-1,j,x); else LCS(i,j-1,x); } int main() { char x[NUM]; char y[NUM]; int m, n; scanf(%d\n, m); for (int i1; im; i) scanf(%c, x[i]); scanf(%d\n, n); for (int i1; in; i) scanf(%c, y[i]); LCSLength(m, n, x, y); printf(%d\n, c[m][n]); LCS(m,n,x); return 0; }最大子段和动态规划问题#include stdio.h #define NUM 1001 int a[NUM]; int MaxSum(int n) { int sum0; int b0; for (int i1;in;i) { if (b0) ba[i]; else ba[i]; if (bsum) sumb; } return sum; } int main() { int n; while (scanf(%d, n) n) { for (int i1; in; i) scanf(%d, a[i]); printf(%d\n, MaxSum(n)); } return 0; }计算最大子段和的动态规划算法的最优解#include stdio.h #define NUM 1001 int a[NUM]; int MaxSum(int n, int besti, int bestj) { int sum0; int b0; int begin 0; for (int i1;in;i) { if (b0) ba[i]; else {ba[i];begin i;} if (bsum) { sum b; besti begin; bestj i; } } return sum; } int main() { int n; int besti, bestj; while (scanf(%d, n) n) { besti 0; bestj 0; for (int i1; in; i) scanf(%d, a[i]); printf(%d\n, MaxSum(n, besti, bestj)); printf(From %d to %d\n, besti, bestj); } return 0; }0-1背包问题动态规划算法#include cstring #include iostream #includectime using namespace std; #define NUM 50 #define CAP 1500 int v[NUM]; int w[NUM]; int p[NUM][CAP]; void knapsack(int c, int n) { int jMaxmin(w[n]-1,c); for( int j0; jjMax; j) p[n][j]0; for( int jw[n]; jc; j) p[n][j]v[n]; for( int in-1; i1; i--) { jMaxmin(w[i]-1,c); for( int j0; jjMax; j) p[i][j]p[i1][j]; for(int jw[i]; jc; j) p[i][j]max(p[i1][j], p[i1][j-w[i]]v[i]); } p[1][c]p[2][c]; if (cw[1]) p[1][c]max(p[1][c], p[2][c-w[1]]v[1]); } void traceback( int c, int n, int x[ ]) { for(int i1; in; i) { if (p[i][c]p[i1][c]) x[i]0; else { x[i]1; c-w[i]; } } x[n](p[n][c])? 1:0; } int main () { int x[NUM]; int W; int n; while (scanf(%d, W) W) { scanf(%d, n); for (int i1; in; i) scanf(%d%d, w[i], v[i]); memset (p, 0, sizeof(p)); knapsack(W, n); printf(%d\n, p[1][W]); traceback(W, n, x); for (int i1; in; i) if (x[i]) printf(%d , i); printf(\n); } return 0; }一维数组#includebits/stdc.h using namespace std; #define NUM 50 #define CAP 1500 int v[NUM]; int w[NUM]; int p[CAP]; int main () { int W,n; while (scanf(%d, W) W) { scanf(%d, n); for (int i1; in; i) scanf(%d%d, w[i], v[i]); memset (p, 0, sizeof(p)); //p(c)ʾcֵ for (int i1; i n; i) for (int c W; c w[i]; c--) if (p[c-w[i]]v[i]p[c]) p[c] p[c-w[i]]v[i]; printf(%d\n,p[W]); //ֵ } return 0; }二维数组#includebits/stdc.h using namespace std; #define NUM 50 #define CAP 1500 int v[NUM]; int w[NUM]; int p[NUM][CAP]; int main () { int W,n; while (scanf(%d, W) W) { scanf(%d, n); for (int i1; in; i) scanf(%d%d, w[i], v[i]); memset (p, 0, sizeof(p)); for (int i 1; i n; i) for (int c W; c 0; c--) if (w[i]c) p[i][c] max(p[i-1][c],p[i-1][c-w[i]]v[i]); else p[i][c] p[i-1][c]; printf(%d\n,p[n][W]); //ֵ } return 0; }最长单调递增子序列动态规划算法#include stdio.h #define NUM 100 int a[NUM]; int LIS_n2(int n) { int b[NUM]{0}; int i,j; b[1] 1; int max 0; for (i2;in; i) { int k 0; for (j1; ji; j) if (a[j]a[i] kb[j]) kb[j]; b[i] k1; if (maxb[i]) maxb[i]; } return max; } int main() { int n; while (scanf(%d, n) n) { for (int i1; in; i) scanf(%d, a[i]); printf(%d\n, LIS_n2(n)); } }数字三角形问题动态规划算法#include stdio.h #define NUM 100 int tri[NUM][NUM]; int triangle(int n) { int i, j; for (in-2; i0; i--) for (j0; ji; j) if( tri[i1][j] tri[i1][j1]) tri[i][j] tri[i1][j]; else tri[i][j] tri[i1][j1]; return tri[0][0]; } int main() { int n; scanf(%d, n); int i, j; for (i0; in; i) for (j0; ji; j) scanf(%d, tri[i][j]); printf(%d\n, triangle(n)); return 0; }