解题思路

核心问题：穷举

关键元素：重叠子问题、最优子结构、状态转移方程

动态规划问题最困难的就是写出这个暴力解，即状态转移方程，优化方法无非是用备忘录或者 DP table。

解决重叠子问题

1.设置备忘录，记录子问题的答案(相当于剪枝)(自顶向下、递归)

509. 斐波那契数

2.DP table，状态转移方程(自底向上、迭代）

f(n)=f(n-1)+f(n-2)

状态压缩

1.斐波那契数中只需要前两个状态，不需要那么长的DP table

2.最长回文子序列，每个位置的值只与周围的值有关。因此将二维DP数组降为一维DP数组。

最优子结构

1.子问题之间必须互相独立

2.改造问题，使其具有最优子结构

状态转移方程

1.确定base case

2.确定状态（原问题和子问题中会变化的变量）

3.确定选择（导致「状态」产生变化的行为）

4.明确dp函数（参数：状态，返回值：题目要求计算的量）

数学归纳思想找状态转移方程

1.明确 dp 数组所存数据的含义

2.根据 dp 数组的定义，运用数学归纳法的思想，假设 dp[0…i-1] 都已知，想办法求出 dp[i]

子序列类问题

解题模板

# 一维DP数组
# dp[i]为以nums[i]为结尾的目标子序列长度
for i in range(len(nums)):
    for j in range(i):
        dp[i] = 最值(dp[i],dp[j] + ...)
        
# 二维DP数组
# 1. dp[i][j]为s1[0...i]和s2[0...j]中的目标子序列（最长公共子序列、编辑距离）
# 2. dp[i][j]为s[i...j]中的目标子序列（最长回文子序列）
m,n = len(s1),len(s2)
dp = [[0 for j in range(n+1)] for i in range(m+1)]
... # 处理 base case
for i in range(1,m+1):
    for j in range(1,n+1):
        if s1[i-1] == s2[j-1]:
            dp[i][j] = dp[i-1][j-1] + ...
        else:
            dp[i][j] = 最值(...)

最长递增子序列 LIS

动态规划 or 二分查找（纸牌游戏）

300. 最长上升子序列

二维递增子序列：信封嵌套问题

354. 俄罗斯套娃信封问题

最大子数组问题

dp[i]为以nums[i]为结尾的最大子数组和

53. 最大子序和

最长公共子序列LCS

dp[i,j]为[0…i-1]与[0…j-1]的LCS长度

1143. 最长公共子序列

583. 两个字符串的删除操作