动态规划

发表于 更新于 分类于

定义

动态规划与分治方法相似，都是通过组合子问题的解来求解原问题。分治方法将问题划分为互不相交的子问题，递归地求解子问题，再将它们的解组合起来，求出原问题的解。与之相反，动态规划应用于子问题重叠的情况，即不同的子问题具有公共的子子问题（子问题的求解是递归进行的，将其划分为更小的子子问题）。动态规划算法对每个子子问题只求解一次，将其保存在一个表格中，避免了这种不必要的计算工作。

动态规划方法通常用来求解最优化问题。这类问题可以有很多可行解，每个解都有一个值，我们希望寻找具有最优值的解。我们称这样的解为问题的一个最优解，因为可能有多个解都达到最优值。

设计方法

通常按如下4个步骤来设计一个动态规划算法：

  1. 刻画一个最优解的结构特征。
  2. 递归地定义最优解的值。
  3. 计算最优解的值，采用自底向上的方法。
  4. 利用计算出的信息构造一个最优解。

经典题目——最长公共子序列问题(LCS)与最长公共子串问题

最长公共子序列问题（LCS问题）

给定两个字符串A和B，长度分别为m和n，要求找出它们最长的公共子序列，并返回其长度。例如：

A = "HelloWorld"
B="loop"

则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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
def LongestSubstring(str1,str2):
    res = 0
    str1_len = len(str1)
    str2_len = len(str2)
    if str1_len == 0 or str2_len == 0:
        return res
    dp = [[0 for j in range(str1_len)] for i in range(str1_len)]
    for i in range(str1_len):
        for j in range(str2_len):
            if str1[i] == str2[j]:
                if i == 0 or j == 0:
                    dp[i][j] = 1
                else:
                    dp[i][j] = dp[i-1][j-1]+1
            else:
                dp[i][j] = max(dp[i-1][j],dp[i][j-1])

    return dp[i][j]

该算法的时间复杂度为$O(n*m)$，空间复杂度为$O(n*m)$。

Note：需要考虑空串的判定条件

最长公共子串问题

给定两个字符串A和B，长度分别为m和n，要求找出它们最长的公共子串，并返回其长度。例如：

A = "HelloWorld"

B = "loop"

则A与B的最长公共子串为 “lo”,返回的长度为2。我们可以看到子序列和子串的区别：子序列和子串都是字符集合的子集，但是子序列不一定连续，但是子串一定是连续的。

整个问题的初始状态为：

相应的状态转移方程为：

代码实现如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
def lcsubstr(str1,str2):
	res = 0
	str1_len = len(str1)
	str2_len = len(str2)
	if str1_len == 0 or str2_len == 0:
		return res
	dp = [[0 for j in range(str1_len)] for i in range(str1_len)]
	for i in range(str1_len):
		for j in range(str2_len):
			if str1[i] == str2[j]:
				if i == 0 or j == 0:
					dp[i][j] = 1
				else:
					dp[i][j] = dp[i-1][j-1]+1
			if dp[i][j]> res:
				res = dp[i][j]
	return res

该算法的时间复杂度为$O(n*m)$ ，空间复杂度为$O(n*m)$。

Note：需要考虑空串的判定条件

参考资料

  • 《算法导论第三版》