定义
动态规划与分治方法相似,都是通过组合子问题的解来求解原问题。分治方法将问题划分为互不相交的子问题,递归地求解子问题,再将它们的解组合起来,求出原问题的解。与之相反,动态规划应用于子问题重叠的情况,即不同的子问题具有公共的子子问题(子问题的求解是递归进行的,将其划分为更小的子子问题)。动态规划算法对每个子子问题只求解一次,将其保存在一个表格中,避免了这种不必要的计算工作。
动态规划方法通常用来求解最优化问题。这类问题可以有很多可行解,每个解都有一个值,我们希望寻找具有最优值的解。我们称这样的解为问题的一个最优解,因为可能有多个解都达到最优值。
设计方法
通常按如下4个步骤来设计一个动态规划算法:
- 刻画一个最优解的结构特征。
- 递归地定义最优解的值。
- 计算最优解的值,采用自底向上的方法。
- 利用计算出的信息构造一个最优解。
经典题目——最长公共子序列问题(LCS)与最长公共子串问题
最长公共子序列问题(LCS问题)
给定两个字符串A和B,长度分别为m和n,要求找出它们最长的公共子序列,并返回其长度。例如:
则A与B的最长公共子序列为 “loo”,返回的长度为3。此处只给出动态规划的解法:定义子问题$dp[i][j]$为字符串A的第一个字符到第 i 个字符串和字符串B的第一个字符到第 j 个字符的最长公共子序列。
为了求解$dp[i][j]$,我们要先判断A的第i个元素B的第j个元素是否相同即判断A[i - 1]和 B[j -1]是否相同,如果相同它就是$dp[i-1][j-1]+ 1$,相当于在两个字符串都去掉一个字符时的最长公共子序列再加 1;否则最长公共子序列取$dp[i][j-1]$和$dp[i-1][j]$中大的那个。
问题的初始状态为:
相应的状态转移方程为:
代码实现如下:
1 | def LongestSubstring(str1,str2): |
该算法的时间复杂度为$O(n*m)$,空间复杂度为$O(n*m)$。
Note:需要考虑空串的判定条件
最长公共子串问题
给定两个字符串A和B,长度分别为m和n,要求找出它们最长的公共子串,并返回其长度。例如:
则A与B的最长公共子串为 “lo”,返回的长度为2。我们可以看到子序列和子串的区别:子序列和子串都是字符集合的子集,但是子序列不一定连续,但是子串一定是连续的。
整个问题的初始状态为:
相应的状态转移方程为:
代码实现如下:
1 | def lcsubstr(str1,str2): |
该算法的时间复杂度为$O(n*m)$ ,空间复杂度为$O(n*m)$。
Note:需要考虑空串的判定条件
参考资料
- 《算法导论第三版》