简述
动态规划是一种将一个复杂问题分解为多个简单的子问题求解的方法。将子问题的答案存储在记忆数据结构中，当子问题再次需要解决时，只需查表查看结果，而不需要再次重复计算，因此节约了计算时间。
国外知乎 Quora 上一个帖子问应该怎样给四岁的孩子解释什么是动态规划，其中一个非常经典的回答如下：
How should I explain dynamic programming to a 4-year-old?
动态规划通常基于一个递推公式和一个或多个初始状态。当前问题的解可以分解为多个子问题解得出。使用动态规划只需要多项式时间复杂度，因为比回溯法和暴力法快很多。
动态规划中非常重要的两个概念：状态和状态转移方程。
下面通过例子由浅至深详细讲解。
所有例题均来自leetcode，所示代码均通过所有测试。
例题目录
不断更新中...
例题
1、最长回文子串
题目描述：
给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。
示例 1：
输入: "babad"
输出: "bab"
注意: "aba" 也是一个有效答案。
算法
定义 dp[i][j] 为 s[i:j+1] 是回文字符串时的长度，如果 s[i:j+1] 不是回文，则 dp[i][j] = 0.
转移方程：
- s[i] == s[j]
dp[i][j] = dp[i+1][j-1] + 2
初始状态：
dp[i][i] = 1
dp[i][i-1] = 2 (s[i] == s[i-1])
代码
class Solution:
def longestPalindrome(self, s: str) -> str:
n = len(s)
dp = [[-1] * n for _ in range(n)]
ans = (0, 0)
for i in range(n):
dp[i][i] = 1
if i > 0 and s[i] == s[i-1]:
dp[i-1][i] = 2
ans = (i-1, i)
for i in range(2, n):
for j in range(0, i-1):
if s[j] == s[i] and dp[j+1][i-1] != -1:
dp[j][i] = dp[j+1][i-1] + 2
if dp[j][i] > ans[1] - ans[0] + 1:
ans = (j, i)
return s[ans[0]:ans[1]+1]
更好理解版本，依次查询长度从小到大
public String longestPalindrome(String s) {
int n = s.length();
if (n == 0) return "";
boolean[][] dp = new boolean[n][n];
int maxLen = 1, startId = 0;
for (int len = 0; len < n; len++) {
for (int i = 0; i < n - len; i++) {
int j = i + len;
if (len == 0) {
dp[i][j] = true;
} else if (len == 1) {
dp[i][j] = (s.charAt(i) == s.charAt(j));
} else {
dp[i][j] = (dp[i+1][j-1] && s.charAt(i) == s.charAt(j));
}
if (dp[i][j] && len + 1 > maxLen) {
maxLen = len + 1;
startId = i;
}
}
}
return s.substring(startId, startId + maxLen);
}
时间复杂度：O(n^2)
类似题目：
转移方程：
s[i] != s[j]
dp[i][j] = max(dp[i][j-1], dp[i+1][j])s[i] == s[j]
dp[i][j] = dp[i+1][j-1] + 2
2、最长有效括号
题目描述：
给定一个只包含 '(' 和 ')' 的字符串，找出最长的包含有效括号的子串的长度。
示例 1:
输入: "(()"
输出: 2
解释: 最长有效括号子串为 "()"
算法
定义 dp[i] 为以 i 结束的最长有效括号长度。
状态转移方程：
- s[i] == '('
dp[i] = 0 - s[i] == ')'
- s[i-1] == '(': dp[i] = dp[i-2] + 2
例如：()() - s[i-1] == ')' and s[i - 1 - dp[i-1]] == '(': dp[i] = dp[i-1] + dp[i - 1 - dp[i-1] - 1] + 2
例如：()(())
注意数组越界情况。
代码
class Solution:
def longestValidParentheses(self, s: str) -> int:
n = len(s)
dp = [0] * n
res = 0
for i in range(1, n):
if s[i] == ')':
if s[i-1] == '(':
if i >= 2:
dp[i] = dp[i-2] + 2
else:
dp[i] = 2
elif i - 1 - dp[i-1] >= 0 and s[i - 1 - dp[i-1]] == '(':
if i - 2 - dp[i-1] >= 0:
dp[i] = dp[i-1] + dp[i - 2 - dp[i-1]] + 2
else:
dp[i] = dp[i-1] + 2
res = max(res, dp[i])
return res
时间复杂度：O(n)
这道题也可以用栈在线性时间范围内解决。
3、最长重复子数组
题目描述：
给两个整数数组 A 和 B ，返回两个数组中公共的、长度最长的子数组的长度。
示例 1:
输入:
A: [1,2,3,2,1]
B: [3,2,1,4,7]
输出: 3
解释:
长度最长的公共子数组是 [3, 2, 1]。
说明:
1 <= len(A), len(B) <= 1000
0 <= A[i], B[i] < 100
题目描述：
dp[i][j] 表示以 A[i] 和 B[j] 结束的公共数组长度。
状态转移：
- A[i] == B[j]
dp[i][j] = dp[i-1][j-1] + 1
代码
class Solution:
def findLength(self, A: List[int], B: List[int]) -> int:
"""
A[i] == B[j] dp[i][j] = dp[i-1][j-1] + 1
"""
m, n = len(A), len(B)
dp = [[0] * (n+1) for _ in range(m+1)]
res = 0
for i in range(1, m+1):
for j in range(1, n+1):
if A[i-1] == B[j-1]:
dp[i][j] = dp[i-1][j-1] + 1
res = max(res, dp[i][j])
return res
时间复杂度：O(mn)
类似题目
子数组变成来子序列，也就是公共的部分可以不是连续的。
dp[i][j] text1[:i] 和 text2[:j] 的最长公共子序列
状态转移：
- text1[i] == text2[j]
dp[i][j] = dp[i-1][j-1] + 1 - text1[i] != text2[j]
dp[i][j] = max(dp[i-1][j], dp[i][j-1])
代码：
class Solution:
def longestCommonSubsequence(self, text1: str, text2: str) -> int:
"""
dp[i][j]
if text1[i] == text2[j]: dp[i][j] = dp[i-1][j-1] + 1
else: dp[i][j] = max(dp[i-1][j], dp[i][j-1])
"""
m, n = len(text1), len(text2)
dp = [[0] * (n+1) for _ in range(m+1)]
for i in range(1, m+1):
for j in range(1, n+1):
if text1[i-1] == text2[j-1]:
dp[i][j] = dp[i-1][j-1] + 1
else:
dp[i][j] = max(dp[i-1][j], dp[i][j-1])
return dp[-1][-1]
7、恢复数组
题目描述：
某个程序本来应该输出一个整数数组。但是这个程序忘记输出空格了以致输出了一个数字字符串，我们所知道的信息只有：数组中所有整数都在 [1, k] 之间，且数组中的数字都没有前导 0 。
给你字符串 s 和整数 k 。可能会有多种不同的数组恢复结果。
按照上述程序，请你返回所有可能输出字符串 s 的数组方案数。
由于数组方案数可能会很大，请你返回它对 10^9 + 7 取余 后的结果。
示例 1：
输入：s = "1000", k = 10000
输出：1
解释：唯一一种可能的数组方案是 [1000]
示例 2：
输入：s = "1317", k = 2000
输出：8
解释：可行的数组方案为 [1317]，[131,7]，[13,17]，[1,317]，[13,1,7]，[1,31,7]，[1,3,17]，[1,3,1,7]
算法
1. 不考虑0，且k足够大时。
以 s = "1317", k = 2000 为例
字符串从下标 1 开始。
i = 0 时，s = ""，dp[0] = 1;
i = 1 时，s = "1"，[1]，dp[1] = 1;
i = 2 时，s = "13"，[1, 3] 和 [13]，dp[2] = dp[1] + dp[0]; 可以理解为 "3" 接在 dp[1] 后面或者 "13" 接在 dp[0] 后面
i = 3 时，s = "131"，dp[3] = dp[2] + dp[1] + dp[0] = 4;
i = 4 时，s = "1317"，dp[4] = dp[3] + dp[2] + dp[1] + dp[0] = 8;
2. 考虑0，且k有限时。
对每次状态转移进行判断是否以 0 开头，是否超出 k 的范围。
代码
class Solution:
def numberOfArrays(self, s: str, k: int) -> int:
mod = 10 ** 9 + 7
n = len(s)
dp = [0] * (n + 1)
dp[0] = 1
for i in range(1, n+1):
for j in range(i-1, -1, -1):
if s[j] == '0':
continue
if int(s[j:i]) <= k:
dp[i] += dp[j]
else:
# 当前字符为0，大于k，且dp[0]为零，可以直接返回0，因为没法构成合适的数字了
if s[i - 1] == "0" and dp[i] == 0:
return 0
break
dp[i] %= mod
return dp[-1]
时间复杂度：两层循环，由于有字符串到数字的强制转换，所以时间会稍微多一些。O(n^2)
空间复杂度：O(n)
8、生成数组
题目描述：
给你三个整数 n、m 和 k 。下图描述的算法用于找出正整数数组中最大的元素。
请你生成一个具有下述属性的数组 arr ：
arr 中有 n 个整数。
1 <= arr[i] <= m 其中 (0 <= i < n) 。
将上面提到的算法应用于 arr ，search_cost 的值等于 k 。
返回上述条件下生成数组 arr 的 方法数 ，由于答案可能会很大，所以 必须 对 10^9 + 7 取余。
示例 1：
输入：n = 2, m = 3, k = 1
输出：6
解释：可能的数组分别为 [1, 1], [2, 1], [2, 2], [3, 1], [3, 2] [3, 3]
提示：
- 1 <= n <= 50
- 1 <= m <= 100
- 0 <= k <= n
算法
根据提示的数据范围，如果DFS搜索答案的话，复杂度是 100^50，显然肯定不是合适的方法。自然想到动态规划。
定义 dp[n][i][k] 表示长度为 n，最大值为 i，search_cost 为 k 的满足条件的方法数，即为所求答案。
状态转移分为两种情况：
- 当最大值 i 位于最后一个元素时，那么方法数为：
- 当最大值出现在前 n-1 个元素之中时：
，乘上 i 表示最后的位置可以在 [1, i] 中任意选择。
初始状态：
dp[0][i][k] = dp[n][0][k] = dp[n][i][k] = 0
dp[1][i][k] = 1
接下来可以写代码了。
代码
class Solution:
def numOfArrays(self, n: int, m: int, k: int) -> int:
mod = 10 ** 9 + 7
memo = {}
def dp(n, i, k):
if n == 0 or i == 0 or k == 0:
return 0
elif n == k == 1:
return 1
if (n, i, k) in memo:
return memo[(n, i, k)]
res = 0
for j in range(1, i):
res += dp(n-1, j, k-1)
res %= mod
res += i * dp(n-1, i, k)
res %= mod
memo[(n, i, k)] = res
return res
res = 0
for i in range(1, m+1):
res += dp(n, i, k)
res %= mod
return res
时间复杂度：需要填满三维数组 dp，O(mnk)
空间复杂度：O(mnk)
