1.动态规划
思想：分治 + 最优子结构
顺推形式：动态递归
vs 递归&分治
共性：找重复子问题
差异性：中途可淘汰次优解

2.常见DP题目和状态方程
爬楼梯： f(n) = f(n-1) + f(n-2), f(1) = 1, f(0) = 0
不同路径： f(x,y) = f(x-1,y) + f(x,y-1)
打家劫舍：dp[i]状态的定义： max $ of robbing A[0 -> i]
dp[i] = max(dp[i - 2] + nums[i], dp[i - 1])
dp[i][0]状态定义：max $ of robbing A[0 -> i] 且没偷 nums[i]
dp[i][1]状态定义：max $ of robbing A[0 -> i] 且偷了 nums[i]
dp[i][0] = max(dp[i - 1][0], dp[i - 1][1]);
dp[i][1] = dp[i - 1][0] + nums[i];
最小路径和：
dp[i][j]状态的定义： minPath(A[1 -> i][1 -> j])
dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + A[i][j]
股票买卖：
dp[i][k][0 or 1] (0 <= i <= n-1, 1 <= k <= K) -- i为天数；K 为
最多交易次数； [0,1]为是否持有股票；总状态数 n * K * 2
初始状态：dp[-1][k][0] = dp[i][0][0] = 0
dp[-1][k][1] = dp[i][0][1] = -infinity
状态转移方程：
dp[i][k][0] = max(dp[i-1][k][0], dp[i-1][k][1] + prices[i])
dp[i][k][1] = max(dp[i-1][k][1], dp[i-1][k-1][0] - prices[i])
3. 高阶DP问题
复杂度来源:
(1) 拥有更多维度
(2) 状态方程更加复杂
编辑距离
如果 word1[i] 与 word2[j] 相同，显然 dp[i][j]=dp[i-1][j-1]

• 如果 word1[i] 与 word2[j] 不同，那么 dp[i][j] 可以通过

1. 在 dp[i-1][j-1] 的基础上做 replace 操作达到目的
2. 在 dp[i-1][j] 的基础上做 insert 操作达到目的
3. 在 dp[i][j-1] 的基础上做 delete 操作达到目的
   取三者最小情况即可

4.字符串
(1) Longest common sequence（最长子序列）
dp[i][j] = dp[i-1][j-1] + 1 (if s1[i-1] == s2[j-1])
else dp[i][j] = max(dp[i-1][j], dp[i][j-1])

(2)Longest common substring (最长子串）
dp[i][j] = dp[i-1][j-1] + 1 (if s1[i-1] == s2[j-1])
else dp[i][j] = 0

(3）字符串匹配算法
暴力法

Rabin-Karp 算法：避免逐字比较
假设子串的长度为 M (pat)，目标字符串的长度为 N (txt)
计算子串的 hash 值 hash_pat
计算目标字符串txt中每个长度为 M 的子串的 hash 值（共需要计算 N-M+1
次）
比较 hash 值：如果 hash 值不同，字符串必然不匹配; 如果 hash 值相同，
还需要使用朴素算法再次判断

KMP算法
当子串与目标字符串不匹配时，
其实你已经知道了前面已经匹配成功那 一部分的字符（包括子串与目标字符串）