背包
题意概要：有 𝑛个物品和一个容量为 𝑊的背包，每个物品有重量 𝑤𝑖和价值 𝑣𝑖两种属性，要求选若干物品放入背包使背包中物品的总价值最大且背包中物品的总重量不超过背包的容量．
01背包
每个物体只能取或者不取（至多1次）
设 DP 状态 𝑓𝑖,𝑗为在只能放前 𝑖个物品的情况下，容量为 𝑗的背包所能达到的最大总价值．
优化空间，注意到fi只和fi-1有关，因此可以去掉一维
dp[v] = 处理过的元素中，凑出的最大价值 （处理元素理解：元素要一个一个处理，处理完第一个后 dp[1]是一个值，处理完第二个元素后 dp[1] 发生变化）
最核心的编码细节：为什么要从右往左遍历？
这是01背包最容易出错、也最值得深想的地方。
假设我们正在处理物品A（重量2，价值6），当前容量 w = 6，要计算：
dp[6] = max(dp[6], dp[6-2] + 6) = max(dp[6], dp[4] + 6)
这里用到的 dp[4] 必须是上一轮（还没放A之前）的值，才代表"前面的物品在容量4时的最优解"。
如果我们从左往右更新，当我们到达 w=6 时，dp[4] 已经在 w=4 这一步被更新过了——它反映的是"放过A之后容量4的最优解"。这样一来，dp[6] 就可能把A计算了两次，退化成完全背包（每件物品可以取无限次）。
从右往左就解决了这个问题：当我们计算 dp[6] 时，我们只往左边看 dp[4]；而 dp[4] 还没有被本轮触碰过，它保留的仍是旧值。大的先更新，就不会"踩到自己的脚印"。
一句话记住：01背包，从右往左；完全背包，从左往右——方向决定物品能被选几次。
分割等和子集
https://leetcode.cn/problems/partition-equal-subset-sum/description/
class Solution {
public boolean canPartition(int[] nums) {
// 含义，递推，初始化，顺序，举例
// 01背包，dp[v] 表示空间v最大的价值
// 针对物品i，dp[v] = max{dp[v],dp[v-w[i]]} dp[v],dp[v-w[i]]表示没放i的
// dp[0] = 0,
// dp[v] = max{dp[v],dp[v-w[i]]} dp[v],dp[v-w[i]]表示没放i的,因此要从右往左便利
int sum = 0;
for(int num:nums){
sum+=num;
}
if (sum%2==1) {
return false;
}
int target = sum/2;
int[] dp = new int[target+1];
for(int i = 0;i<nums.length;i++){
for(int v = target;v>=nums[i];v--){
dp[v] = Math.max(dp[v], nums[i]+dp[v-nums[i]]);
}
}
return dp[target]==target;
}
}
最后一块石头的重量 II
https://leetcode.cn/problems/last-stone-weight-ii/description/
class Solution {
public int lastStoneWeightII(int[] stones) {
// 含义，递推，初始化，顺序，举例
// 找到最接近 sum/2的价值，背包容量sum/2，每个物品价值和重量相等
// 01背包，每个元素只能使用1次
// dp[v] 表示容量v能装的最大价值
// 针对i个物品，dp[v] = max{dp[v],v[i]+dp[v-v[i]]} 右侧的是选i之前的
// dp[0] =0;
// 从右到左
int sum = 0;
for(int stone:stones){
sum+=stone;
}
int volum = sum/2;
int[] dp = new int[volum+1];
dp[0] = 0;
for(int i =0;i<stones.length;i++){
for(int v = volum;v>=stones[i];v--){
dp[v] = Math.max(dp[v], stones[i]+dp[v-stones[i]]);
}
}
return sum-2*dp[volum];
}
}
一和零
https://leetcode.cn/problems/ones-and-zeroes/description/
- 注意
a>=cnt0[i]b>=(strs[i].length()-cnt0[i])
class Solution {
public int findMaxForm(String[] strs, int m, int n) {
// 每个元素只能用1次，01背包，strs中物品价值是i，v（空间/代价）是0和1的个数,背包容量是m，n
// dp含义，递推，初始化，顺序，举例
// dp[a][b] 表示最多用a个0b个1可以获取的最大子集个数
// 针对物品i， dp[a][b] =max(dp[a][b], 1+dp[a-i.0个数][b-i.1个数])
// dp[0][0] = 0,
// 从右下往左上
int[] cnt0 = new int[strs.length];
for(int i = 0;i<strs.length;i++){
for(char c:strs[i].toCharArray()){
if (c=='0') {
cnt0[i]++;
}
}
}
int[][] dp = new int[m+1][n+1];
dp[0][0] = 0;
for(int i = 0;i<strs.length;i++){
for(int a = m;a>=cnt0[i];a--){
for(int b = n;b>=(strs[i].length()-cnt0[i]);b--){
dp[a][b] = Math.max(dp[a][b], 1+dp[a-cnt0[i]][b-(strs[i].length()-cnt0[i])]);
}
}
}
return dp[m][n];
}
}
目标和
- 转化为找和为goal方案个数的问题
- ==注意方案个数问题dp[0] 经常为1而非0== https://leetcode.cn/problems/target-sum/description/
class Solution {
public int findTargetSumWays(int[] nums, int target) {
// 假设right部分添加负号，left+right = sum， left-right = target
int sum = 0;
for(int num:nums){
sum+=num;
}
if((sum+target)%2==1) return 0;
int goal =(sum+target)/2;
if(goal<0) return 0;
// 从中选一部分和为goal即可，有几种选法
// 01背包问题，加和等于goal限制下个数最多，容量：goal，元素体积 nums[i] 价值1
// dp[v] = 从当前处理过的元素中，凑出和为 v 的方案数。
// 针对第i个物品，dp[v] = dp[v]+dp[v-v[i]] 等式右侧是没有选过i的旧值
// dp[0]=0
// 从右到左
int[] dp = new int[goal+1];
dp[0] = 1; // 凑出0本身就是一种方案
for(int i = 0;i<nums.length;i++){
for(int v = goal;v>=nums[i];v--){
dp[v] = dp[v]+dp[v-nums[i]];
}
}
return dp[goal];
}
}
完全背包
- 便利顺序要从左到右
- 为什么这样可以保证 wi 可以被取多次，
- 因为 f(i,j-wi) 已经被 f(i,j-wi-wi) 更新过了
零钱兑换 II
https://leetcode.cn/problems/coin-change-ii/description/
- 每个元素可以被用多次，属于完全背包，注意便利顺序即可
- 注意方案个数问题，dp[0] 经常为1而非0
class Solution {
public int change(int amount, int[] coins) {
// 完全背包，容量amount，元素体积coin[i]
// dp[v] 表示在处理过的元素中 凑成v和组合数量
// 针对第i个元素，dp[v] = dp[v]+dp[v-v[i]]
// dp[0] = 1;
// 从左到右
int[] dp = new int[amount+1];
dp[0] = 1;
for(int i = 0;i<coins.length;i++){
for(int v=coins[i] ;v<=amount;v++){
dp[v] = dp[v]+dp[v-coins[i]];
}
}
return dp[amount];
}
}
组合总和 Ⅳ
https://leetcode.cn/problems/combination-sum-iv/description/ 为什么循环顺序决定了这个差异？
完全背包（你的写法）：外层枚举元素 i，意思是"我现在决定元素 nums[i] 用几次"。因为每个元素只被考虑一次作为"主角"，自然消除了顺序。
排列计数（正确写法）：外层枚举容量 v，意思是"对于目标和为 v 的序列，我枚举最后一个放入的元素是谁"。这样 [1,2] 和 [2,1] 会分别通过"最后放2"和"最后放1"两条路径被统计，顺序就被区分开了。
class Solution {
public int combinationSum4(int[] nums, int target) {
// 完全背包，容量 target，元素体积 nums[i] 价值？
// dp[v] = 已经处理过的元素中组成v的排列个数
// for i dp[v] = dp[v]+dp[v-v[i]]
// dp[0] = 1;
// ->
// 因为是排列个数：因此外层枚举体积，内岑枚举 已经处理了那些元素
int[] dp = new int[target+1];
dp[0] = 1;
for(int v =1 ;v<=target;v++){
for(int i = 0;i<nums.length;i++){
if(v>=nums[i]) dp[v] = dp[v]+dp[v-nums[i]];
}
}
return dp[target];
}
}
零钱兑换
class Solution {
public int coinChange(int[] coins, int amount) {
// 完全背包，容量：amount，元素体积 coins[i],代价 1
// 针对已经遍历的元素 dp[v] = 凑成v需要的最小个数
// for i : dp[v] = min(dp[v],1+dp[v-v[i]])
// dp[0] = inf
// 内外都可，->
int[] dp = new int[amount+1];
dp[0] = 0;
for(int i = 1;i<=amount;i++) dp[i] = Integer.MAX_VALUE;
for(int i = 0;i<coins.length;i++){
for(int v = coins[i];v<=amount;v++){
if(dp[v-coins[i]]!=Integer.MAX_VALUE){
dp[v] = Math.min(dp[v], 1+dp[v-coins[i]]);
}
}
}
return dp[amount]==Integer.MAX_VALUE?-1:dp[amount];
}
}
完全平方数
- 因为是min，因此除了dp[0]的位置要设置成MAX。 https://leetcode.cn/problems/perfect-squares/description/
class Solution {
// 返回n的 完全平方数最少数量,
public int numSquares(int n) {
// 计数dp，nums= [1,4,9,16...], 完全背包，容量 n，元素体积nums[i],代价1
// dp[v] = 已经遍历的元素中凑成v的最小数量
// for i : dp[v] = min(dp[v],1+dp[v-v[i]])
// dp[0] = 0, 其他位置 = MAX
// 内外都可，-》
int[] dp = new int[n+1];
dp[0] = 0;
for(int i = 1;i<n+1;i++){
dp[i] = Integer.MAX_VALUE;
}
int sqrt = (int)Math.sqrt(n);// 1,2,3...sqrt
for(int i = 0;i<sqrt;i++){
for(int v = (i+1)*(i+1);v<=n;v++){
if(dp[v-(i+1)*(i+1)]==Integer.MAX_VALUE) continue;
dp[v] = Math.min(dp[v], 1+dp[v-(i+1)*(i+1)]);
}
}
return dp[n];
}
}
单词拆分
class Solution {
public boolean wordBreak(String s, List<String> wordDict) {
// 完全背包，
// dp[v] = 处理完前i个后，针对字符串长度v能否由dic组成
// for i : dp[v] = dp[v]||dp[v-i.len]&&s[v-i.len+1:v]==dic[i]
// dp[0] = true
// 只能内部是元素，因为dp[v] 因该用到所有的单词，不应该依赖前i个单词，便利顺序：-》
boolean[] dp = new boolean[s.length()+1];
dp[0] =true;
for(int v =0 ;v<=s.length();v++){
for(int i =0;i<wordDict.size();i++){
if(v<wordDict.get(i).length()) continue;
dp[v] = dp[v]||(dp[v-wordDict.get(i).length()]&&s.substring(v-1-wordDict.get(i).length()+1, v).equals(wordDict.get(i)));
}
}
return dp[s.length()];
}
}
多重背包
挖宝石
你是一名探险家，进入了一座宝石矿洞。矿洞中共有 `c` 种宝石，每种宝石有各自的挖取时间、价值和数量限制。你总共有 `t` 分钟的时间，请你计算在时间限制内能获得的**最大总价值**。
**输入格式：**
- `int t`：总可用时间
- `int c`：宝石种类数
- `int[] time`：长度为 `c`，`time[i]` 表示挖取第 `i` 种宝石需要的时间
- `int[] value`：长度为 `c`，`value[i]` 表示第 `i` 种宝石的价值
- `int[] count`：长度为 `c`，`count[i]` 表示第 `i` 种宝石的可用数量
**输出：** 在时间 `t` 内可以获得的最大总价值。
- 内层先循环k次，里面的t的循环会被整体执行k次，每次都可以选取一个c[i]类物品
public class GemMining {
public static int maxValue(int T, int C, int[] time, int[] value, int[] count) {
int[] dp = new int[T + 1];
for (int i = 0; i < C; i++) {
// 把第i种宝石展开成count[i]个独立物品，每个做一次0/1背包
for (int k = 0; k < count[i]; k++) {
// 0/1背包：逆序遍历，防止同一件物品被选多次
for (int t = T; t >= time[i]; t--) {
dp[t] = Math.max(dp[t], dp[t - time[i]] + value[i]);
}
}
}
return dp[T];
}
}
背包总结
- 确定dp定义，一般是体积作为变量，dp[v] ，v不是下标而是容量（往往是长度，体积等等）
- 确定递推关系
- 01背包
- 完全背包
- 确定便利顺序
- 01背包，容量从大到小，完全背包容量从小到大
- 内外层的顺序
- 先物品后体积：针对无序的情况（组合）
- 先体积后物品：针对有序（排列）
- 必须要内层物品的情况：==因为每个位置的答案依赖的是"更小位置的完整答案"，而不是"只用某几个元素的答案"。== 比如单词拆分，dp[v] 不应该依赖用了几个单词i，dp[v] 应该和所有候选单词关联，所以必须是内层单词外层背包容量
- 确定初始值
- 求最大值往往是dp[0] = 0
- 求方案数量往往是dp[0] = 1
- 求最小值时除了0以外的位置是否要设置成MAX，求最大值时除了0意外的位置是否要设置成MIN
计数型背包元素体积是nums[i] ，没有价值的概念，只是计数，而最大值最小值有价值概念，一般两个数组，如果一个数组可能价值和体积是等价的
| 问题类型 | 外层循环 | 内层循环 | 容量方向 | 含义 |
|---|---|---|---|---|
| 01 背包最大值 | 物品 | 容量 | 倒序 | 每个物品最多用一次 |
| 完全背包最大值 | 物品 | 容量 | 正序 | 每个物品可以无限用 |
| 组合数，完全背包 | 物品 | 容量 | 正序 | 不区分顺序 |
| 排列数，完全背包 | 容量 | 物品 | 正序 | 区分顺序 |
| 01 背包方案数 | 物品 | 容量 | 倒序 | 每个物品最多选一次 |
基本都是物品在外，只有排列数是物品在内；容量的方向01是倒序，完全是正序
其他
树状dp
https://leetcode.cn/problems/house-robber-iii/description/
class Solution {
public int rob(TreeNode root) {
int[] ans = rob1(root);
return Math.max(ans[0], ans[1]);
}
private int[] rob1(TreeNode root) {
if (root == null) {
return new int[] { 0, 0 };
}
// 先把左右子树结果存起来，每棵子树只递归一次
int[] left = rob1(root.left);
int[] right = rob1(root.right);
// 抢当前节点：左右子节点都不能抢（取各自的 index 0）
int tou = root.val + left[0] + right[0];
// 不抢当前节点：左右子节点各自取最优
int butou = Math.max(left[0], left[1]) + Math.max(right[0], right[1]);
return new int[] { butou, tou };
}
}
状态dp
买卖股票的最佳时机 II https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-ii/description/
class Solution {
public int maxProfit(int[] prices) {
// dp[i][0] = 第i天结束时没有股票的总利润，dp[i][1] = 第i天有股票的总利润
// dp[i][0] = max(dp[i-1][0],dp[i-1][1]+price[i]), dp[i][1] = max(dp[i-1][1],dp[i-1][0]-price[i])
// dp[0][0]=0, dp[0][1] = -price[0]
// ->
// a:前一天没有股票的利润，b前一天有股票时的利润
// a：0，b：-price【0】
int a = 0;
int b = -prices[0];
for(int i = 1;i<prices.length;i++){
int prea = a;
int preb = b;
a = Math.max(prea, preb+prices[i]);
b = Math.max(preb, prea-prices[i]);
}
return a;
}
}
买卖股票的最佳时机含冷冻期 https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-with-cooldown/
class Solution {
public int maxProfit(int[] prices) {
if (prices.length == 0) return 0;
int n = prices.length;
int[][] dp = new int[n][2];
// 第0天
dp[0][0] = 0;
dp[0][1] = -prices[0];
// 第1天（防止 i-2 越界）
if (n > 1) {
dp[1][0] = Math.max(dp[0][0], dp[0][1] + prices[1]); // 卖或不卖
dp[1][1] = Math.max(dp[0][1], -prices[1]); // 买或不买
}
// 第2天起标准转移
for (int i = 2; i < n; i++) {
dp[i][0] = Math.max(dp[i-1][0], dp[i-1][1] + prices[i]); // 卖出：昨天可持
dp[i][1] = Math.max(dp[i-1][1], dp[i-2][0] - prices[i]); // 买入：前天无票（昨天冷冻）
}
return dp[n-1][0];
}
}
区间dp
- 特征：研究一个连续区间
- 关键词：子串，区间，合并相邻元素，切割，回文，从两端取，最后一步在区间内部选一个点
典型模板：外层控制区间长度（一般是大区间依赖小区间），内层控制区间起点
for (int len = 1; len <= n; len++) {
for (int i = 0; i + len - 1 < n; i++) {
int j = i + len - 1;
// 根据题目转移
}
}
枚举分割点
for(int len = 3;len<=n;len++){
for(int i = 0;i+len-1<=n-1;i++){
int j = i+len-1;
dp[i][j] = Integer.MAX_VALUE;
for(int k = i;k<=j;k++){
dp[i][j] = Math.min(
dp[i][j],
dp[i][k]+dp[k][j]+values[i]*values[j]*values[k]
);
}
}
}
最长回文子串
- 初始化被放到了遍历中
class Solution {
public String longestPalindrome(String s) {
// 区间dp，外层len，内层起点
// dp[i,j] = s[i,j]是否为回文串
// dp[i,j] = s[i]==s[j]&&dp[i+1,j-1]
// len<=2: s[i]==s[j]?true,false
// len 从小到大，i从小到大
int n = s.length();
boolean[][] dp = new boolean[n][n];
int l=0,ansLen = 0;
for(int len = 1;len<=n;len++){
for(int i = 0;i+len-1<=n-1;i++){
int j = i+len-1;
if (s.charAt(i)==s.charAt(j)) {
if (len<=2||dp[i+1][j-1]) {
dp[i][j] = true;
if (len>ansLen) {
ansLen = len;
l = i;
}
}
}
}
}
return s.substring(l, l+ansLen);
}
}
回文子串
初始化被隐藏在了for循环中：len<=2
class Solution {
public int countSubstrings(String s) {
// 定义：dp[i][j] 代表s[i:j]是否为回文串
// 转移：dp[i][j] = s[i]==s[j] && dp[i+1][j-1]
// 初始化：dp[i][i] = true, dp[i][i+1] = true/false
// 遍历顺序：长度大的依赖长度小的，因此按长度从小到大
int n = s.length();
boolean[][] dp = new boolean[n][n];
int count = 0;
for(int len = 1;len<=n;len++){
for(int i = 0;i+len-1<=n-1;i++){
int j = i+len-1;
if (s.charAt(i)==s.charAt(j)) {
if (len<=2||dp[i+1][j-1]) {
dp[i][j] = true;
count++;
}
}
}
}
return count;
}
}
最长回文子序列
区间dp，外层是len，内层起点，注意初始化被放在了循环内部
class Solution {
public int longestPalindromeSubseq(String s) {
// 区间dp
// dp[i,j] = s[i,j]最长子序列的长度
// if s[i]==s[j] dp[i,j] = dp[i+1,j-1]+2 else dp[i,j] = max(dp[i,j-1],dp[i+1,j])
// len<=2 if s[i]==s[j] dp[i,j] = len;
// len从小到大，起点从小到大
int n = s.length();
int[][] dp = new int[n][n];
int ans = 0;
for(int len = 1;len<=n;len++){
for(int i = 0;i+len-1<=n-1;i++){
int j = i+len-1;
if (len<=2&&s.charAt(i)==s.charAt(j)) {
dp[i][j] = len;
}else{
if (s.charAt(i)==s.charAt(j)) {
dp[i][j] = 2+dp[i+1][j-1];
}else{
dp[i][j] = Math.max(dp[i][j-1], dp[i+1][j]);
}
}
ans = Math.max(ans, dp[i][j]);
}
}
return ans;
}
}
石子游戏
class Solution {
public boolean stoneGame(int[] piles) {
// 区间dp
// dp[i,j] 表示 区间先手的领先得分（净得分）
// dp[i,j] = max（p[i]-dp[i+1,j],p[j]-dp[i,j-1];
// init：长为1时直接返回 p[i]
// len 从小到大，i从左到右
int n = piles.length;
int[][] dp = new int[n][n];
for(int len = 1;len<=n;len++){
for(int i = 0;i+len-1<=n-1;i++){
int j =i+len-1;
if (len==1) {
dp[i][j] = piles[i];
}else{
dp[i][j] = Math.max(piles[i]-dp[i+1][j], piles[j]-dp[i][j-1]);
}
}
}
return dp[0][n-1]>0;
}
}
戳气球
枚举最后一个戳破的是哪个即可（也就是最内层的k），注意此时因为k是最后一个被戳破的，因此k的邻居应该是 i-1 和 j+1
class Solution {
public int maxCoins(int[] nums) {
// 区间dp
// dp[i,j] 表示区间i，j可以获得的硬币最大数量
// dp[i,j] for k(最后戳破的气球位置) : dp[i,j] = max(nums[k]*nums[i-1]*nums[j+1]+dp[i,k-1]+dp[k+1][j],dp[i,j])
// len==1
// len 从1开始，i从1开始,i+len-1《=n-2
int[] arr = new int[nums.length+2];
int n = arr.length;
arr[0]=1;arr[n-1] = 1;
for(int i = 0;i<nums.length;i++) arr[i+1] = nums[i];
int ans = 0;
int[][] dp = new int[n][n];
for(int len=1;len<=n-2;len++){
for(int i = 1;i+len-1<=n-2;i++){
int j = i+len-1;
for(int k = i;k<=j;k++){
dp[i][j] = Math.max(dp[i][j], arr[k]*arr[i-1]*arr[j+1]+dp[i][k-1]+dp[k+1][j]);
}
ans = Math.max(ans, dp[i][j]);
}
}
return ans;
}
}
切棍子的最小成本
注意内层的k是第一刀的位置，不是最后一刀 为什么：举个例子：
棍子长度 10 cuts = [2, 4, 7] 如果你说最后切的是 2，那么在切 2 之前，4 和 7 已经切了。 但是切 4 和 7 的成本，不是只发生在 [2, 10] 这个区间里，因为那个时候 2 还没切，左边仍然连着。所以内层枚举的是第一刀
class Solution {
public int minCost(int n, int[] cuts) {
// 区间dp arr[0,....n]
// dp[i,j] 为(i,j) 之间的所有切割点的切割最小成本
// dp[i,j] = for k（k是第一次切割位置） : dp[i,j] = min(dp[i,j],arr[j]-arr[i] + dp[i,k]+dp[k,j])
// len=2 dp[i,j] = 0
// len 从2到arr.len, i从0开始
int[] arr = new int[cuts.length + 2];
arr[arr.length - 1] = n;
Arrays.sort(cuts);
for (int i = 0; i < cuts.length; i++)
arr[i + 1] = cuts[i];
int[][] dp = new int[arr.length][arr.length];
int INF = 1_000_000_000;
for (int len = 2; len <= arr.length; len++) {
for (int i = 0; i + len - 1 <= arr.length - 1; i++) {
int j = i + len - 1;
dp[i][j] = INF;
if (len == 2) {
dp[i][j] = 0;
continue;
}
for (int k = i + 1; k < j; k++) {
dp[i][j] = Math.min(dp[i][j], arr[j] - arr[i] + dp[i][k] + dp[k][j]);
}
}
}
return dp[0][arr.length - 1];
}
}
多边形三角剖分的最低得分
class Solution {
public int minScoreTriangulation(int[] values) {
// 区间dp
// dp含义，dp[i,j]=nums[i,j]区间最小分数
// 转移：dp[i,j] = min(dp[i,k],dp[k,j] 和 （i，k，j） )
// 初始化：len>=3
int n = values.length;
int[][] dp = new int[n][n];
for(int len = 3;len<=n;len++){
for(int i = 0;i+len-1<=n-1;i++){
int j = i+len-1;
dp[i][j] = Integer.MAX_VALUE;
for(int k = i+1;k<=j-1;k++){
dp[i][j] = Math.min(
dp[i][j],
dp[i][k]+dp[k][j]+values[i]*values[j]*values[k]
);
}
}
}
return dp[0][n-1];
}
}
合并石头的最低成本
class Solution {
public int mergeStones(int[] stones, int k) {
// 每次合并会少k-1个， 所以一个区间长度为len的合并到最后是 （len-1）%（k-1）+1
// 区间dp， 从后往前思考，最后一次合并是从k堆合并到1堆，那这个k堆分为1堆和k-1堆；另外一个区间能合并到多少堆其实已经确定了：(len-1)%(k-1)+1
// dp[i,j] = stones[i:j]合并到最后的成本（不关心最后剩多少，因为剩多少已经由len固定了）
// dp[i,j] = 枚举分割点k《[i,j] 使得 [i,k] [k+1,j] 其中我们保证 [i,k]一定能合成一堆
// 初始化：默认是Integer max
// 顺序：len从小到大，起点从小到大，k从小到大
int n = stones.length;
if((n-1)%(k-1)!=0) return -1;
int[] pre = new int[n+1];
for(int i = 0;i< n;i++){
pre[i+1] = pre[i]+stones[i];
}
int INF = 1_000_000_000;
int[][] dp = new int[n][n];
for(int len = k;len<=n;len++){
for(int i = 0;i+len-1<=n-1;i++){
int j = i+len-1;
dp[i][j] = INF;
for(int m = i;m<j;m+=k-1){ // 每次加k-1保证[i,m]能被k-1整除因而合为一堆,
dp[i][j] = Math.min(dp[i][j], dp[i][m]+dp[m+1][j]);
}
// 上面的m循环是将i-j分为两部分，分别计算各自内部的成本，还没合起来，下面才是合起来
if ((j-i)%(k-1)==0) {
dp[i][j]+=pre[j+1]-pre[i];
}
}
}
return dp[0][n-1];
}
}
区间dp总结
- 初始化：一般不初始化，在循环中通过判断len来进行初始化
- 外层len：一般从1开始
- 内层i：从0开始
- 内层k：一般是[i,j]中间的一个数，将区间分为两部分，至于说是这个k是第一次某个操作还是最后一次某个操作取决于：关键看：枚举这个位置 k 之后，左右两边能不能变成两个互不影响的子问题。
- 比如戳气球：如果k作为这个区间第一次戳的，那么左边区间的最右边一个的代价计算时需要考虑右侧区间的左边某个气球，右侧同理，所以k不能是第一次戳这个操作的位置，应该是最后一次，因为k是最后一次戳的操作在[i,j] 因此这个代价是 i-1和j+1，而左侧区间最右边的气球的代价计算时右侧的要乘以的数一定是num[k]（因为k是最后戳的），因此左侧不依赖于右侧；
- 比如切棍子：
- 如果k是最后一次切割：左边切割时要计算成本，而成本需要知道这次切割的长度，而k这个位置还没有切割，所以左边某次切割会用到右边的切割顺序，左右关联
- 如果k是第一次切割，左边和右边完全分离开来了
线性/前缀型dp
- 特征：从左到右处理数组或字符串，dp[i] 表示处理到第 i 个位置时的某种答案。
- 关键词：数组，字符串
dp[i] 从 dp[i-1]、dp[i-2] 转移而来
dp[i] = max(dp[j] + something)
爬楼梯
class Solution {
public int climbStairs(int n) {
// 线性dp
// dp[i] 爬到第i阶有多少种方法
// dp[i] = dp[i-1]+dp[i-2]
// dp[0] =1, dp[1] = 1;
// i从2到n
if(n<=1) return 1;
int[] dp = new int[n+1];
dp[0] = 1;dp[1] =1;
for(int i = 2;i<=n;i++){
dp[i] = dp[i-1]+dp[i-2];
}
return dp[n];
}
}
最大子数组和
class Solution {
public int maxSubArray(int[] nums) {
// 前缀dp
// dp[i] 以i结尾的最大子数组和
// dp[i] = dp[i-1]>0?dp[i-1]+nums[i]:nums[i]
// dp[0] = nums[0]
// i从1-n-1
int n = nums.length;
int[] dp = new int[n];
dp[0] = nums[0];
int ans = dp[0];
for(int i = 1;i<n;i++){
dp[i] = dp[i-1]>0?(dp[i-1]+nums[i]):nums[i];
ans = Math.max(ans, dp[i]);
}
return ans;
}
}
双序列 DP
- 特征：题目有两个字符串、两个数组，或者两个序列之间的匹配关系。
- 关键词：两个字符串，两个数组，一个串是否能由另一个串变来，一个串是否是另一个串的子序列，两个序列的相似度、距离、匹配数量
dp[i][j] 表示 text1 的前 i 个字符 和 text2 的前 j 个字符之间的答案
- DP 的本质是枚举所有可能的"最后一个决策"，把大问题拆成若干个更小的子问题。 而"用还是不用当前这个元素"几乎永远是一个合法的最后决策，因为它把问题规模从 i 缩小到了 i-1。
最长公共子序列
class Solution {
public int longestCommonSubsequence(String text1, String text2) {
// 双序列dp
// dp[i,j] s1前i个字符串和s2前j个字符串的最长子序列长度
// dp[i,j] = if s1[i-1]==s2[j-1] dp[i-1][j-1]+1 else max(dp[i][j-1],dp[i-1][j])
// dp[0][0] = 0
// 先i后j，i：1-s1.len, j:1-s2.len
int[][] dp = new int[text1.length()+1][text2.length()+1];
dp[0][0] = 0;
for(int i = 1;i<=text1.length();i++){
for(int j =1;j<=text2.length();j++){
dp[i][j] = text1.charAt(i-1)==text2.charAt(j-1)?(1+dp[i-1][j-1]):Math.max(dp[i][j-1], dp[i-1][j]);
}
}
return dp[text1.length()][text2.length()];
}
}
最长重复子数组
class Solution {
public int findLength(int[] nums1, int[] nums2) {
// 双序列dp
// dp[i,j] n1前i个数和n2前j个数 最长重复子数组
// dp[i,j] = if n1[i-1]==n2[j-1] 1+dp[i-1][j-1]
// dp[0][0] = 0;
// i:1-n1.len , j:1-n2.len
int[][] dp = new int[nums1.length+1][nums2.length+1];
int ans = 0;
for(int i = 1;i<=nums1.length;i++){
for(int j = 1;j<=nums2.length;j++){
if(nums1[i-1]==nums2[j-1]){
dp[i][j] = 1+dp[i-1][j-1];
ans = Math.max(ans, dp[i][j]);
}
}
}
return ans;
}
}
两个字符串的删除操作
class Solution {
public int minDistance(String word1, String word2) {
// 前缀dp
// dp[i,j] 表示s1前i个字符和s2前i个字符的最小操作次数
// dp[i,j] = if s[i]==s2[j] dp[i-1,j-1] else min(1+dp[i-1,j], 1+dp[i,j-1])
// dp[0,0] = 0, dp[i,0] = i, dp[0,j] = j
// 先i后j，0-s1.len, 0-s2.len
int[][] dp = new int[word1.length()+1][word2.length()+1];
int INF = 1_000_000_000;
for(int i = 0;i<=word1.length();i++){
for(int j = 0;j<=word2.length();j++){
dp[i][j] = INF;
if (i==0||j==0) {
if(i==0) dp[i][j] = j;
if(j==0) dp[i][j] = i;
}else{
dp[i][j] = word1.charAt(i-1)==word2.charAt(j-1)?dp[i-1][j-1]:Math.min(1+dp[i-1][j], 1+dp[i][j-1]);
}
}
}
return dp[word1.length()][word2.length()];
}
}
编辑距离
class Solution {
public int minDistance(String word1, String word2) {
// 双序列dp
// dp[i,j] s1前i个字符和s2前j个字符的最小操作数
// 序列1的前i个和序列2的前j个实现一致的最后一部操作可能是插入，删除，替换三个操作从其他状态转移过来的，如果插入说明序列1前i个和序列2前j-1个已经一致，在序列1末尾插入即可，1+dp[i][j-1]
// dp[i,j] = if s1[i]==s2[j] dp[i-1,j-1] else min(dp[i,j-1]+1,1+dp[i-1,j],1+dp[i-1,j-1])
// dp[0,0] =0;,dp[i,0] = i, dp[0,j] = j
// 先i后j， i:0-s1.len, j:0-s2.len
int[][] dp = new int[word1.length()+1][word2.length()+1];
for(int i = 0;i<=word1.length();i++){
for(int j = 0;j<=word2.length();j++){
if(i==0||j==0){
if(i==0) dp[i][j] = j;
if(j==0) dp[i][j] = i;
}else{
int temp = Math.min(Math.min(1+dp[i][j-1], 1+dp[i-1][j]), 1+dp[i-1][j-1]);
dp[i][j] = word1.charAt(i-1)==word2.charAt(j-1)?dp[i-1][j-1]:temp;
}
}
}
return dp[word1.length()][word2.length()];
}
}
不同的子序列
class Solution {
public int numDistinct(String s, String t) {
// 双序列dp
// dp[i,j] s1前i个字符中s2前j个字符作为子序列的出现次数
// dp[i,j] = if s1[i-1]==s2[j-1] dp[i-1][j-1]+dp[i-1][j] 用不用s[i-1]来匹配j-1，两种情况加起来 else dp[i-1][j]
// dp[0,0] = 1 , dp[i,0] = 1 (aa,a =dp[1,0]+dp[1,1]) = 2 , dp[0,j] = 0;
// i 从0-s1.len , j: 0-s2.len
int[][] dp = new int[s.length()+1][t.length()+1];
dp[0][0] =1;
for(int i = 1;i<=s.length();i++){
for(int j = 0;j<=t.length();j++){
if(j==0){
dp[i][j] = 1;
}else{
if (s.charAt(i-1)==t.charAt(j-1)) {
dp[i][j] = dp[i-1][j-1]+dp[i-1][j];
}else{
dp[i][j] = dp[i-1][j];
}
}
}
}
return dp[s.length()][t.length()];
}
}
交错字符串
class Solution {
public boolean isInterleave(String s1, String s2, String s3) {
// 双序列dp
// dp[i,j] s1前i个字符+s2的前j个字符能否组成s3的前 i+j
// dp[i,j] =if s1[i-1]!=s2[j-1] : if s3[i+j-1]==s1[i-1] dp[i-1][j] else
// dp[i][j-1] else dp[i-1][j]||dp[i,j-1]
// dp[0][0] = true dp[0,j] : s2[0:j-1]==s3[0:j-1] dp[i,0] = s1[0:i-1]==s3[0:i-1]
// i: 1-s1.len j:s2.len
if(s1.length()+s2.length()!=s3.length()) return false;
boolean[][] dp = new boolean[s1.length() + 1][s2.length() + 1];
for (int i = 0; i <= s1.length(); i++) {
for (int j = 0; j <= s2.length(); j++) {
if (i == 0 || j == 0) {
if (i == 0 && j == 0) {
dp[i][j] = true;
} else {
if (i == 0)
dp[i][j] = s2.substring(0, j).equals(s3.substring(0, j));
if (j == 0)
dp[i][j] = s1.substring(0, i).equals(s3.substring(0, i));
}
} else {
if (s3.charAt(i + j - 1) == s1.charAt(i - 1) || s3.charAt(i + j - 1) == s2.charAt(j - 1)) {
if (s1.charAt(i - 1) == s2.charAt(j - 1)) {
dp[i][j] = dp[i - 1][j] || dp[i][j - 1];
} else {
dp[i][j] = s3.charAt(i + j - 1) == s1.charAt(i - 1) ? dp[i - 1][j] : dp[i][j - 1];
}
}
}
}
}
return dp[s1.length()][s2.length()];
}
}
状态机dp
- 特征：题目有明显的“状态切换”。比如：持有股票 / 不持有股票，今天冷冻期 / 不在冷冻期，已经买了几次 / 卖了几次，当前在第几种状态，当前颜色是什么，当前是否处于某种限制中
dp[i][state] 表示第 i 天处于 state 状态下的最优答案
买卖股票的最佳时机
class Solution {
public int maxProfit(int[] prices) {
// 状态机dp，持有股票/未持有股票
// dp[i,0/1] 第i（1-n）天结束时持有股票/不持有股票的利润
// dp[i,0] = max(dp[i-1,0],dp[i-1,1]+price[i-1]),dp[i,1] = max(dp[i-1,1],-price[i-1])注意不是dp[i-1,0]-price[i-1]因为只能买卖一次
// dp[0,0] = 0, dp[0,1] = -INF
// i: 1-n;
int n = prices.length;
int[][] dp = new int[n+1][2];
dp[0][0] = 0;
int INF = 1_000_000_000;
dp[0][1] = -INF;
for(int i = 1;i<=n;i++){
dp[i][0] = Math.max(dp[i-1][0], dp[i-1][1]+prices[i-1]);
dp[i][1] = Math.max(dp[i-1][1], -prices[i-1]);
}
return dp[n][0];
}
}
买卖股票的最佳时机 II
class Solution {
public int maxProfit(int[] prices) {
// 状态机dp，持有/不持有
// dp[i,0/1] 第i天结束时不持有/持有的最大利益
// dp[i,0] = max(dp[i-1,0],dp[i-1,1]+prices[i-1]) dp[i,1] = max(dp[i-1,0]-price[i-1],dp[i-1,1]) 注意和121题的区别
// dp[0,0]= 0 dp[0,1] =-INF
// i: 1-n
int n = prices.length;
int[][] dp = new int[n+1][2];
int INF = 1_000_000_000;
dp[0][0] = 0;dp[0][1] = -INF;
for(int i = 1;i<=n;i++){
dp[i][0] = Math.max(dp[i-1][0], prices[i-1]+dp[i-1][1]);
dp[i][1] = Math.max(dp[i-1][0]-prices[i-1], dp[i-1][1]);
}
return dp[n][0];
}
}
买卖股票的最佳时机 IV
- 注意初始化的位置
class Solution {
public int maxProfit(int k, int[] prices) {
// 状态dp
// buy[i,j] 前i天恰好进行j次交易且手上有股票，sell[i,j] 前i天恰好进行j次交易且没股票
// buy[i,j] = max(buy[i-1,j],sell[i-1][j]-price[i-1]) sell[i,j] =
// max(sell[i-1,j],buy[i-1,j-1]+price[i-1])
// buy[0,j] = -INF sell[0,j] = 0
// i:0-price.len, j:0-k
int n = prices.length;
int[][] buy = new int[n + 1][k + 1];
int[][] sell = new int[n + 1][k + 1];
int INF = 1_000_000_000;
for (int j = 0; j <= k; j++)
buy[0][j] = -INF;
for (int j = 1; j <= k; j++)
sell[0][j] = -INF;
for (int i = 1; i <= prices.length; i++) {
buy[i][0] = Math.max(buy[i-1][0], sell[i-1][0]-prices[i-1]);
for (int j = 1; j <= k; j++) {
buy[i][j] = Math.max(buy[i - 1][j], sell[i - 1][j] - prices[i - 1]);
sell[i][j] = Math.max(sell[i - 1][j], buy[i - 1][j - 1] + prices[i - 1]);
}
}
int ans = 0;
for(int j = 0;j<=k;j++) ans = Math.max(ans, sell[n][j]);
return ans;
}
}
买卖股票的最佳时机含冷冻期
class Solution {
public int maxProfit(int[] prices) {
// 状态机dp
// dp[i,0/1/2] 第i（1-n）天结束时不持有但可以买入/今天刚卖出/不持有股票但可以买入
// dp[i,0] = max(dp[i-1,0],dp[i-1,1]) dp[i,1] = dp[i-1,0] dp[i,2] = max(dp[i-1,0]-price[i-1],dp[i-1,1]-price[i-1])
// dp[0,0] = 0; dp[0,1] = -INF, dp[0,2] = -INF;
// i:1-n;
int n = prices.length;
int[][] dp = new int[n+1][3];
int INF = 1_000_000_000;
dp[0][0] = 0;dp[0][1] = -INF;dp[0][2] = -INF;
for(int i = 1;i<=n;i++){
dp[i][0] = Math.max(dp[i-1][0], dp[i-1][1]);
dp[i][1] = dp[i-1][2]+prices[i-1];
dp[i][2] = Math.max(dp[i-1][2], dp[i-1][0]-prices[i-1]);
}
return Math.max(dp[n][0], dp[n][1]);
}
}
dp总结
- 先看是不是dp
- 有选择：比如：选不选这个物品，当前字符匹不匹配，走上面还是走左边，买还是不买股票，切不切这一刀
- 当前问题可以由更小的问题推出，比如：前
i个数的答案，能不能由前i-1个数推出，字符串[0...i]的答案，能不能由更短的字符串推出，容量为j的背包，能不能由容量更小的背包推出
- 找阶段（dp中的i和j代表问题推进的阶段）
| 题目类型 | 阶段通常是什么 |
|---|---|
| 数组 | 前 i 个元素 |
| 字符串 | 前 i 个字符 |
| 背包 | 前 i 个物品、容量 j |
| 路径问题 | 到达位置 (i, j) |
| 区间问题 | 区间 [i, j] |
| 股票问题 | 第 i 天、持有/不持有 |
| 子序列问题 | 考虑到第 i 个元素 |
| 树形 DP | 以某节点为根的子树 |
- 计数问题，往往空串ans是1
- DP 的本质是枚举所有可能的"最后一个决策"，把大问题拆成若干个更小的子问题。 而"用还是不用当前这个元素"几乎永远是一个合法的最后决策，因为它把问题规模从 i 缩小到了 i-1。
- 在写方程之前，先做这一步：用语言描述一个具体方案里最后发生了什么。
- 初始化：可以枚举边界也就是 i=0（或其他边界维度）时，逐一问每个 dp_0_j：这个场景在现实中能发生吗？(参考买卖股票的最佳时机 IV)