适用动态规划的特点
所解决的问题是最优化问题。
所解决的问题具有“最优子结构”。可以建立一个递推关系，使得n阶段的问题，可以通过几个kb? a:b
int D[MAX][MAX];//记录最长公共子序列的长度
int S[MAX];//记录其中一个公共最长子序列
void countLen(int A[], int n, int B[], int m) {//根据公式填写D[i][j]
int i, j;
for (i = 1; i <= n; i++)//i=0,j=0不用
for (j = 1; j <= m; j++)
if (A[i] == B[j])
D[i][j] = D[i - 1][j - 1] + 1;
else
D[i][j] = max(D[i - 1][j], D[i][j - 1]);
}
int searchS(int A[], int n, int B[], int m) {//如果D[i]j]==D[i-1][j-1]+1，则A[i]可写进S;
int i, j, k;
i = n;
j = m;
k = D[n][m];
while (i != 0 && j != 0) {
if (D[i][j] == D[i - 1][j - 1])
i--;
else if (D[i][j] == D[i][j - 1])//也可沿着D[i][j]==d[i-1][j]回溯
j--;
else
{
S[k--] = A[i];
i--;
j--;
}
}
//返回最长长度
return D[m][n];
}
其他问题
最大字段和问题
矩阵连乘问题
数据压缩问题
0-1背包问题
最优二叉树搜索问题
【原创声明。转载请标注原文地址：https://blog.csdn.net/yunyunyx/article/details/84140780】
【原创声明】转载请标明出处：https://www.cnblogs.com/surecheun/https://www.cnblogs.com/surecheun/p/9973932.html
