适用动态规划的特点
所解决的问题是最优化问题.
所解决的问题具有 "最优子结构". 可以建立一个递推关系, 使得 n 阶段的问题, 可以通过几个 k<n 阶段的低阶子问题的最优解来求解.
具有 "重叠子结构" 的特点. 即, 求解低阶子问题时存在重复计算.
词典法
大家都知道, 递归算法一般都存在大量的重复计算, 这会造成不必要的时间浪费. 词典法, 它可以使递归函数避免重复计算. 词典法的具体做法是, 设计一个数据结构 D(多为数组)来保存以前的计算结果. 在计算过程中, 如果发现要用到的计算结果是之前已经算过了的结果时, 就可以直接从数据结构 D 中获取, 避免重复计算, 用空间换取时间.
动态规划同样使用了类似 "词典法" 的措施, 也设计了一个数据结构来保存计算结果, 但不再使用递归函数来求解, 而是通过循环迭代的方式来填写数据结构.
动态规划常见问题
最长公共子序列
如果序列 { s1, s2, ......, sk } 是序列 { a1, a2, ......, an } 的子序列, 又是序列 { b1, b2, ......, bm } 的子序列, 则称序列 s 为序列 a 和 序列 b 的公共子序列. 在 a 和 b 的所有公共子序列中, 长度最长者称为最长公共子序列. 求 a,b 的最长公共子序列.
解析: 一个长度为 n 的序列, 有 2 的 n 次方个子序列; 如果用穷举的方法来比的话, 那么时间复杂度将会非常高. 很明显这是一个最优化的问题, 我们不妨看看这期间存不存在递推关系, 尝试寻找一下 "最优子结构".
假设 S={s1,s2,...sk}是序列 A={a1,a2,...an}和 B={b1,b2...bm}的最长子序列, 那么有以下发现:
如果 an=bm, 则 {s1,s2...s(k-1)} 是{a1,a2,...a(n-1)}和 {b1,b2,...b(m-1)} 的最长子序列;
如果 an!=bm, 则 S 要么是 A(n-1)和 B 的最长公共子序列, 要么是 A 和 B(m-1)的最长公共子序列.
根据上面的分析, 此问题存在着递推关系 ("最优子结构"). 为方便, 先计算最长公共子序列的长度, 然后再寻找最长公共子序列. 考虑用一个 二维数组 D[i][j] 来记录 A(i),B(j) 的最长公共子序列的长度. 由上面的分析, 很容易得到以下:
D[i][j]=0, 如果 i 或 j 为 0;
D[i][j]=D[i-1][j-1]+1, 如果 ai=bj;
D[i][j]=max(D[i-1][j],D[i][j-1]), 如果 ai!=bj
由上面的递推公式可知, D[i][j]的计算有可能要用到 i,j 位置上一行的数以及 i,j 位置所在行左边的数, 所以填写 D[i][j]是应该是由上往下, 由左往右填写, 最后的 D[n][m]就是 A 和 B 的最长公共子序列的长度.
C++ 实现如下:
- #define MAX 100
- #define max(a,b) a>b? 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://www.cnblogs.com/surecheun/p/9973932.html