动态规划
动态规划三要素
重叠子问题:重复计算
最优子结构:通过子问题的最值得到原问题的最值
-
状态转移方程:列出正确的「状态转移方程」才能正确地穷举
#初始化 base case dp[0][0][...] = base #进行状态转移 for 状态1 in 状态1的所有取值: for 状态2 in 状态2的所有取值: for ... dp[状态1][状态2][...] = 求最值(选择1,选择2...)
1、确定 base case。
2、确定「状态」,也就是原问题和子问题中会变化的变量。
3、确定「选择」,也就是导致「状态」产生变化的行为,即「选择」。
4、明确 dp 函数/数组的定义。
基本动态规划:一维
-
509.斐波那契数(简单)
状态转移方程:dp[i] = dp[i - 1] + dp[i - 2],可使用状态压缩 -
322.零钱兑换(中等)
状态转移方程:dp[i] = min(dp[i], 1 + dp[i - coin]); -
70. 爬楼梯(简单)
状态转移方程:dp[i] = dp[i-1] + dp[i-2],可使用状态状态压缩 -
198. 打家劫舍(简单)
状态转移方程:dp[i]=max(nums[i-1]+dp[i-2],dp[i-1]),可使用状态压缩 -
413. 等差数列划分(中等)
状态转移方程:dp[i] = dp[i-1]+1,需要对dp表求和得到最终的结果
基本动态规划:二维
输入是二维时,定义二维的dp数组
-
64. 最小路径和(中等)
状态转移方程:if(i==0&&j==0) dp[0][0] = grid[0][0]; else if(i==0) dp[i][j] = dp[i][j-1] + grid[i][j]; else if(j==0) dp[i][j] = dp[i-1][j] + grid[i][j]; else dp[i][j] = Math.min(dp[i-1][j],dp[i][j-1]) + grid[i][j];
542. 01 矩阵
两个方向的状态转移方程:
dp[i][j] = Math.min(dp[i][j],dp[i-1][j]+1);
dp[i][j] = Math.min(dp[i][j],dp[i][j-1]+1);
dp[i][j] = Math.min(dp[i][j],dp[i+1][j]+1);
dp[i][j] = Math.min(dp[i][j],dp[i][j+1]+1);
-
221. 最大正方形
状态转移方程:
dp[i][j] = Math.min(Math.min(dp[i-1][j],dp[i][j-1]),dp[i-1][j-1])+1;
maxEdge = Math.max(maxEdge,dp[i][j]);
子序列问题
300. 最长递增子序列
base case: dp[i] = 1
状态转移方程:
for(int j = 0;j < i;j++){
if(nums[i] > nums[j]){
dp[i] = Math.max(dp[j]+1,dp[i]);
}
}
354. 俄罗斯套娃信封问题
信封嵌套问题就需要先按特定的规则排序,之后就转换为一个 最长递增子序列问题。先对宽度 w 进行升序排序,如果遇到 w 相同的情况,则按照高度 h 降序排序。之后把所有的 h 作为一个数组,在这个数组上计算 LIS 的长度就是答案。
1143. 最长公共子序列
dp数组定义:dp[i][j]含义是对于s1[0..i-1]和s2[0..j-1],LCS长度是dp[i][j]
base case:dp[0][:]和dp[:][0]初始化为0,表示空串
状态转移方程:
if(text1.charAt(i-1)==(text2.charAt(j-1)))
dp[i][j] = dp[i-1][j-1]+1;
else
dp[i][j] = Math.max(dp[i-1][j],dp[i][j-1]);
编辑距离问题
72. 编辑距离
状态转移方程:相等不变,不等增删改
if(word1.charAt(i-1)==word2.charAt(j-1))
dp[i][j] = dp[i-1][j-1];
else{
dp[i][j] = min(dp[i-1][j-1]+1,dp[i][j-1]+1,dp[i-1][j]+1);
}
最大子数组问题
53. 最大子序和
dp数组定义 :dp[i]表示以nums[i]结尾的最大子数组和。
状态转移方程:dp[i] = Math.max(dp[i],dp[i-1]+nums[i]);
base case:dp[0] = nums[0];
516. 最长回文子序列
dp定义比较特殊:在子串s[i...j]中,最长回文子序列的长度为dp[i][j]
1312. 让字符串成为回文串的最少插入次数
回文串的dp定义基本相同:dp[i][j]表示i-j子串的相应值
状态转移方程:
if(s.charAt(i)==s.charAt(j))
dp[i][j] = dp[i+1][j-1];
else
dp[i][j] = Math.min(dp[i+1][j], dp[i][j-1]) + 1;
背包问题
0-1背包
dp[i][j] 表示前i个物品,背包容量为j时,能装下的最大价值
base case:dp[0][:] = dp[:][0]=0.表示0个物品或者0容量,最大价值为0
状态转移方程:
if(num[i-1] > j )
dp[i][j]=dp[i-1][j]
else
dp[i][j]=Math.max(dp[i-1][j],dp[i-1][j-nums[i-1]+vals[i-1]);
子集背包
416. 分割等和子集
先求和得sum,转化为背包问题:对N个物品,sum/2的容纳重量,每个物品的重量为nums[i],是否存在一种装法,可以将背包装满?
dp[i][j] 表示 对容量为j的背包,使用i个物品可以将其装满
base case: dp[:][0]=true:没有空间相当于装满了,dp[0][:]=false:没有物品,不可能装满
状态转移方程:
if(nums[i-1] > j)
dp[i][j] = dp[i-1][j];
else
dp[i][j] = dp[i-1][j] || dp[i-1][j-nums[i-1]];
完全背包:物品数量无限
518. 零钱兑换 II
分割类型题
数据结构
二叉树
124. 二叉树中的最大路径和
105. 从前序与中序遍历序列构造二叉树
二叉搜索树
700. 二叉搜索树中的搜索
701. 二叉搜索树中的插入操作
98. 验证二叉搜索树
450. 删除二叉搜索树中的节点
99. 恢复二叉搜索树
完全二叉树
222. 完全二叉树的节点个数
序列化和反序列化二叉树