算法总结之动态规划（DP）

适用动态规划的特点

所解决的问题是最优化问题。
所解决的问题具有“最优子结构”。可以建立一个递推关系，使得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://blog.csdn.net/yunyunyx/article/details/84140780】

巴特西

算法总结之动态规划（DP）

适用动态规划的特点

词典法

动态规划常见问题

最长公共子序列

其他问题

最新文章

热门文章