学习篇|leetcode刷题笔记-DP篇

----代码随想录笔记

题型1、基础动态规划

战略：

基础dp通常通过总结数学规律，如斐波拉契数列这种比较容易观察到的规律。例题没什么好说的，难以总结共性。

典型例题：

746. 使用最小花费爬楼梯
 509. 斐波那契数
 70. 爬楼梯
 62. 不同路径
 63. 不同路径 II
343. 整数拆分
 96. 不同的二叉搜索树

题型2、0-1背包

战略：

0-1背包的原理需要掌握，以及滚动数组的优化。在做具体的题目，一般会有变形，以下是变形例子：
1、在背包容量限制下，能装到的最大价值。这个是背包问题能直接套用的，但是要搞清楚题目中哪个是容量，哪个是价值，哪个是重量。
2、方案数。是背包问题的经典变形，是不能直接套用原背包递推公式的。

经典例题：

416. 分割等和子集

关键词:

如果能够分割成2个子集，那么一定存在子集和为数组之和的一半。

问题转化：

在容量是（sum/2）的背包下，求能装到的最大价值，价值数组和重量数组都是nums。因为最大的容量是（sum/2）,那么如果能够分割成2个子集，最大容量是一定能够填满的。最后的判断依据就是dp[capacity]==capatity?

细节：

如果sum/2不能被整除，在nums是正整数的情况下，是可以直接返回false的。

class Solution {
    public boolean canPartition(int[] nums) {
        int sum = Arrays.stream(nums).sum();
        if (sum%2!=0) {
            return false;
        }
        int capacity = sum/2;
        int[] dp = new int[capacity+1];
        for (int i=0; i<nums.length; ++i) {
            for (int j=capacity; j>=nums[i]; --j) {
                dp[j] = Math.max(dp[j], dp[j-nums[i]]+nums[i]);
            }
        }
        return dp[capacity]==capacity;
    }
}

1049. 最后一块石头的重量 II

关键词：

尽可能平分成2。换个方式理解，分成三堆a,a,b，其中2堆是重量一样的。total_weight = a+a+b, 如何使得b最小的问题，b>=0, 所以a最大取值是total_weight/2.

问题转化：同416

class Solution {
    public int lastStoneWeightII(int[] stones) {
        int sum = Arrays.stream(stones).sum();
        int capacity = sum/2;
        int[] dp = new int[capacity+1];
        for (int i=0; i<stones.length; ++i) {
            for (int j=capacity; j>=stones[i]; --j) {
                dp[j] = Math.max(dp[j], dp[j-stones[i]]+stones[i]);
            }
        }
        return sum-dp[capacity]*2;
    }
}

494. 目标和

关键词：

1、方案数的求解问题。
2、推导思路，如果数组分成两个部分，两个部分的加和分别是a,b，那么有：
a-b=target
a+b=sum,sum为数组的和
所以a的值是可以确定的a=(sum+target)/2.

问题转化：

本题是求方案数，个人感觉其实很难想到套用0-1背包，原递推公式是不可以直接套用的，方案数有自己的递推公式，具体见代码。

细节：

1、对于target可能是负数，那么capacity也可能是负的，但是题中nums[i]>=0，所以capacity一定要是正的。
2、不能被整除的问题，类似416
3、dp的初始值问题。与0-1背包不同，方案数都只与dp相关，如果没有初始值，那么结果只能是0.

class Solution {
    public int findTargetSumWays(int[] nums, int target) {
        int sum = Arrays.stream(nums).sum()+target;
        if (sum%2!=0) {
            // 都是整数，不能凑成非整数
            return 0;
        }
        int capacity = sum/2;
        if (capacity<0) capacity = capacity;
        int[] dp = new int[capacity+1];
        dp[0]=1;
        for (int i=0; i<nums.length; ++i) {
            for (int j=capacity; j>=nums[i]; --j) {
                dp[j] += dp[j-nums[i]];
            }
        }
        return dp[capacity];
    }
}

474. 一和零

关键词：

非多重背包，因为每个元素只能使用一遍，这个是2维的0-1背包。

问题转化：

直接套用0-1背包递推公式，搞清楚以下问题：
重量是什么？每个元素的0，1个数
价值是什么？元素的个数，能放进背包的即+1
容量是什么？m，n

class Solution {
    public int findMaxForm(String[] strs, int m, int n) {
        int[] count0 = new int[strs.length];
        int[] count1 = new int[strs.length];
        for (int i=0; i<strs.length; ++i) {
           String str = strs[i];
           for (int j=0; j<str.length(); ++j) {
               if (str.charAt(j)=='0') {
                   count0[i]++;
               } else {
                   count1[i]++;
               }
           }
        }

        int[][] dp = new int[m+1][n+1];
        
        for (int i=0; i<strs.length; ++i) {
            for (int x=m; x>=count0[i]; --x) {
                for (int y=n; y>=count1[i]; --y) {
                    dp[x][y] = Math.max(dp[x][y],dp[x-count0[i]][y-count1[i]]+1);
                }
            }
        }
        return dp[m][n];
    }
}

以上代码可以优化成：

class Solution {
    public int findMaxForm(String[] strs, int m, int n) {
        int[][] dp = new int[m+1][n+1];
        for (int i=0; i<strs.length; ++i) {
            String str = strs[i];
            int zeroNum = 0;
            int oneNum = 0;
            for (char ch:str.toCharArray()) {
                if (ch == '0') {
                    zeroNum++;
                } else {
                    oneNum++;
                }
            }

            for (int x=m; x>=zeroNum; --x) {
                for (int y=n; y>=oneNum; --y) {
                    dp[x][y] = Math.max(dp[x][y], dp[x-zeroNum][y-oneNum]+1);
                }
            }
        }
        return dp[m][n];
    }
}

题型3、完全背包

战略：

完全背包的原理，换元的推导方法，以及滚动数组的优化。具体的题目有以下变形：
1、直接套用完全背包的公式。
2、方案数，方案数有又分组合数和排序数，组合是先背包后容量。排序数是先容量后背包。
3、利用换元法推导出来的。这种感觉都不像是背包问题了。

经典例题：

518. 零钱兑换 II

关键词：

1.组合方案数

问题转化：

无论是0-1，还是完全，方案数的递推公式是dp[j]+=dp[j]+dp[j-nums[i]
推导过程：
dp[i][j] , 到第i个数位置，价值为j的方案数有dp[i][j]个
dp[i][j] = $\sum$ dp[i-1][j-k*nums[i]]

dp[i][j-nums[i]] = $\sum$ dp[i-1][j-(k+1)*nums[i]]

dp[i][j] = dp[i-1][j] + dp[i][j-nums[i]]

降维优化：和完全背包的思路一样，不写了。结果是：dp[j] = dp[j] + dp[j-nums[i]]

细节：

1、与0-1相似，方案数一定要初始话dp[0] = 1; 方案数完全通过dp转的，所以如果没有初始化，结果一定是0.

class Solution {
    public int change(int amount, int[] coins) {
        int[] dp = new int[amount+1];
dp[0] = 1;
        for (int i=0; i<coins.length; ++i) {
            for (int j=coins[i]; j<=amount; ++j) {
                dp[j] = dp[j] + dp[j-coins[i]];
            }
        }
        return dp[amount];
    }
}

377. 组合总和 Ⅳ

关键词：

1、排序方案数

问题转化：

与518不一样的是，518不用考虑顺序，而此题需要。
例子：
如果是零钱{2,3}, 组合成5的方式有，如果是518那么就是1，而此题则为2.

为什么for循环的先后顺序会有两种不同的结果呢？以👆的例子分析。i是背包，j是容量。

组合：先背包后容量

倒数第2次遍历，i=0，j=2～5，这个循环结束后，dp = {1,0,1,0,1,0}, 单从含义来理解，就是到2这个数位置，组成0，2，4分别有一种方式，其他为0.
最后一次遍历，i=1，j=3～5，j=4时，dp={1,0,1,1,1,0}, j=5时，dp={1,0,1,1,1,1}, dp[5]的位置只被计算了一遍。

排序：先容量后背包

倒数第2次外循环遍历，j=4，i=0～1，这个外循环结束后，dp={1,0,1,1,1,0}，单从含义理解，就是到3这个数，组合成0，2，3，4分别有1种方法。
最后一次外循环遍历，j=5，i=0～1，在这个循环中，可以看到dp[5]的位置被计算了两遍，先加上了dp[2],后加上了dp[3]。先加了dp[2]，表示组合为2的方案数之后自己补3；再加上了dp[3]，表示组合为3的方案数之后自己补2，从这里看出来，排序方案数时不在乎顺序的；而组合方案数只考虑了加上dp[3]，后面自己补2。
———
感觉这里关于顺序的思考还没有触达本质，后面再想想吧。

细节：

1、求方案数要初始化，第三遍了～

class Solution {
    public int combinationSum4(int[] nums, int target) {
        int[] dp = new int[target+1];
        dp[0] = 1;
        for (int j=1; j<=target; ++j) {
            for(int i=0; i<nums.length; ++i) {
                if (j>=nums[i]) {
                dp[j] = dp[j] + dp[j-nums[i]];

                }
            }
        }
        return dp[target];
    }
}

322. 零钱兑换

关键词：

1、求min的推导，类似完全背包问题

问题转化：

推导过程：
dp[i][j]:到第i个数为止，组合成j的硬币的个数
dp[i][j] = min(dp[i-1][j], dp[i-1][j-v[i]]+1, dp[i-1][j-2v[i]]+2, ···)
dp[i][j-v[i]] = min(dp[i-1][j-v[i]], dp[i-1][j-2v[i]]+1, dp[i-1][j-3*v[i]]+2, ···)
dp[i][j] = min(dp[i-1][j], dp[i][j-v[i]]+1);

细节：

1、初始化问题，因为是求min的，所以要初始化为最大值占位，这个站位可以认为找不到方案，又因为dp[0]是推导的开始，所以要初始化为一个有意义的值，dp[0]=0


class Solution {
    public int coinChange(int[] coins, int amount) {
        int[] dp = new int[amount+1];
        Arrays.fill(dp, Integer.MAX_VALUE);
        dp[0] = 0;
        for (int i=0; i<coins.length; ++i) {
            for (int j=coins[i]; j<=amount; ++j) {
                if (dp[j - coins[i]] != Integer.MAX_VALUE) {
                dp[j] = Math.min(dp[j], dp[j-coins[i]]+1);

                }
            }
        }
        return dp[amount] == Integer.MAX_VALUE ? -1:dp[amount];
    }
}

279. 完全平方数

类似322，跳过

139. 单词拆分

关键词：dp定义+推导

问题转化：

这一题感觉不是很想背包，和322一样，推导的过程中和背包很像。
推导：
dp[i]:字符串前i个字符能否被拆分
dp[i+1]的递推：
dp[0]==true && 0～i（包含i）是否存在字典数组中或
dp[1]==true && 1～i（包含i）是否存在字典数组中或
···
dp[i]==true && i～i(包含i) 是否存在字典数组中


class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        boolean[] dp = new boolean[s.length()+1];
        dp[0] = true;
        for (int i=1; i<dp.length; ++i) {
            for (int j=0; j<i; ++j) {
                String tmp = s.substring(j, i);
                if (wordDict.contains(tmp) && dp[j] == true) {
                    dp[i] = true;
                }
            }
        }
        return dp[s.length()];
    }
}

题型4、打家劫舍

战略：

每家有且只有2种选择，偷or不偷，所以要有2维数组来存储状态。在遍历顺序上，根据前面的值算出当前值。

经典例题

198. 打家劫舍

关键词：


class Solution {
    public int rob(int[] nums) {
        int[][] dp = new int[2][nums.length];
        dp[0][0] = 0;
        dp[1][0] = nums[0];
        for (int i=1; i<nums.length; ++i) {
            dp[0][i] = Math.max(dp[0][i-1], dp[1][i-1]);
            dp[1][i] = dp[0][i-1]+nums[i];
        }
        return Math.max(dp[0][nums.length-1], dp[1][nums.length-1]);
    }
}

213. 打家劫舍 II

关键词：
1、环形，类似于滑动窗口的思想，固定长度的窗口，只考虑窗口内部的


class Solution {
    public int rob(int[] nums) {
        if (nums.length==1) {
            return nums[0];
        }
        if (nums.length==2) {
            return Math.max(nums[0], nums[1]);
        }
        int result1 = robWithInterval(nums, 1, nums.length-2);
        int result2 = robWithInterval(nums, 2, nums.length-1);
        return Math.max(result1, result2);
    }
    
    public int robWithInterval(int[] nums, int start, int end) {
        if (start>end) {
            return 0;
        }
        int[][] dp = new int[2][nums.length];
        dp[0][start-1] = 0;
        dp[1][start-1] = nums[start-1];
        for (int i=start; i<=end; ++i) {
            dp[0][i] = Math.max(dp[0][i-1], dp[1][i-1]);
            dp[1][i] = dp[0][i-1]+nums[i];
        }
        return Math.max(dp[0][end], dp[1][end]);
    }
}

337. 打家劫舍 III

关键词：

1、后序遍历
2、依旧需要2维数组来表示状态，2维数组包含了2个信息，一个是下标表示是否偷，一个是值表示偷到的金额


/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public int rob(TreeNode root) {
        int[] res = robDfs(root);
        return Math.max(res[0], res[1]);
    }
    
    public int[] robDfs(TreeNode root) {
        int[] res = new int[2];
        if (root==null) {
            return res;
        }
        int[] left = robDfs(root.left);
         int[] right = robDfs(root.right);
        res[0] = Math.max(left[0], left[1]) + Math.max(right[0], right[1]);
        res[1] = left[0]+right[0]+root.val;
        return res;
    }
}

题型5、股票买卖

战略：

需要用数组来表示不同状态下的股票情况，这点和打家劫舍类似。数组的状态主要有一下几种：
1、持有、不持有，这里有个问题：如果当天卖掉了，算持有吗？--不算。这种分法主要是只有对买卖的次数没有要求。
2、如果对买卖的次数有要求，就要明确是第几次买卖。
3、冷冻期的情况，就要分成：买入、卖出、冷冻这3中情况。

经典例题：

121. 买卖股票的最佳时机

关键词：

1、只能买卖一次

问题转化：

是战略里面的第一种，需要记录2种状态

细节

只能买卖一次，怎么体现这个一次？下一题讲到。

122. 买卖股票的最佳时机 II

关键词：

细节

初始化的问题，第一天，第2次买入可以理解在第一天买入-卖出-买入。

188. 买卖股票的最佳时机 IV

关键词：

1、限制次数

问题转化

是123的抽象版

309. 最佳买卖股票时机含冷冻期

关键词：

1、冷冻期

问题转化：

是战略里面的第三种。

题型6、子序列

战略：

1、一定要确定dp数组的定义，下标和值各有定义。
关于定义，我怎么知道要怎么定义呢？
a.如果题目要求是递增或者递减, 不管是否有子序列是否连续的要求，一般都要定义为：以第i个结尾的最长子序列的长度是dp[i].一般dp种的最大值是所求。

b.如果题目要求子序列不连续：遍历到第i个为止（不一定以i结尾）的子序列的长度是dp[i].一般dp[length-1]就是所求。

c.如果题目要求子序列连续：以第i个结尾的连续子序列的长度是dp[i].一般dp种的最大值是所求。

注意以上b，c两种区别，它们的递推公式差异也很大。
如果是b，一般是和遍历到的所有都有关系，一般是max（xxx）这种。
如果是c，一般只和dp[i-1]相关。

2、确定递推公式的时候，要学会怎么划分，要做到不重不漏，但是有例外，就是求min，max的情况下，重复不会影响结果的。但是最好还是按照不重不漏的标准来划分情况，然后推导公式。

关键词：

1、求公共子序列的变形，只要长度和s一致就好了

问题转化：

也像应用题，其实本质和1143一样，代码稍作改动。

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

关键词：

1、最小值

问题转化：

是求公共子序列的变形，所以先要确定dp，dp[i][j],word1长度是i，word2长度是j，需要达到相等，所需要删除元素的最少次数。

实现细节：

dp长度还是length+1，但是这里的首行首列需要初始化了，它是有意义的。

class Solution {
    public int minDistance(String word1, String word2) {
        int[][] dp = new int[word1.length() + 1][word2.length() + 1];
        for (int i = 0; i < word1.length() + 1; i++) dp[i][0] = i;
        for (int j = 0; j < word2.length() + 1; j++) dp[0][j] = j;
        
        for (int i = 1; i < word1.length() + 1; i++) {
            for (int j = 1; j < word2.length() + 1; j++) {
                if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1];  // 相等，可以作为公共子序列的一部分，所以不需要额外的操作
                }else{
                    dp[i][j] = Math.min(dp[i - 1][j - 1] + 2,
                                        Math.min(dp[i - 1][j] + 1, dp[i][j - 1] + 1));  // 不可以作为公共子序列的一部分，只能删掉了
                }
            }
        }
        
        return dp[word1.length()][word2.length()];
    }
}

53. 最大子数组和

关键词：

1、连续

问题转化：

不要求递增，但是要求连续，是战略中c的类别。dp定义：dp[i]：以第i个数结尾的最大连续子序列和为dp[i]。

115. 不同的子序列

关键词：

问题转化：

这一题比较特别，感觉不是很好套模型。先给出dp定义
注意这里不考虑实现细节的优化！！！
dp[i][j]：以i为结尾的s子序列中出现以j为结尾的t的个数为dp[i][j]。

s[i]==t[j]，
s[i]!=t[j], 那么t(0_{j)出现在s(0}i)中的次数，和出现在(0~i-1)中一样的。比如t=ab，s=abc，当j=1， i=2时。

实现细节：

init dp长度是length+1, 同时注意首列的初始化为1

class Solution {
    public int numDistinct(String s, String t) {
        int[][] dp = new int[s.length() + 1][t.length() + 1];
        for (int i = 0; i < s.length() + 1; i++) {
            dp[i][0] = 1;
        }
        
        for (int i = 1; i < s.length() + 1; i++) {
            for (int j = 1; j < t.length() + 1; j++) {
                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()];
    }
}

最后编辑于：2022.05.07 21:16:27

人面猴
序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
沈念sama阅读 212,332评论 6赞 493
死咒
序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
沈念sama阅读 90,508评论 3赞 385
救了他两次的神仙让他今天三更去死
文/潘晓璐我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
开封第一讲书人阅读 157,812评论 0赞 348
道士缉凶录：失踪的卖姜人
文/不坏的土叔我叫张陵，是天一观的道长。经常有香客问我，道长，这世上最难降的妖魔是什么？我笑而不...
开封第一讲书人阅读 56,607评论 1赞 284
港岛之恋（遗憾婚礼）
正文为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
茶点故事阅读 65,728评论 6赞 386
恶毒庶女顶嫁案：这布局不是一般人想出来的
文/花漫我一把揭开白布。她就那样静静地躺着，像睡着了一般。火红的嫁衣衬着肌肤如雪。梳的纹丝不乱的头发上，一...
开封第一讲书人阅读 49,919评论 1赞 290
城市分裂传说
那天，我揣着相机与录音，去河边找鬼。笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。我是一名探鬼主播，决...
沈念sama阅读 39,071评论 3赞 410
双鸳鸯连环套：你想象不到人心有多黑
文/苍兰香墨我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
开封第一讲书人阅读 37,802评论 0赞 268
万荣杀人案实录
序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
沈念sama阅读 44,256评论 1赞 303
护林员之死
正文独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋以下内容为张勋视角年9月15日...
茶点故事阅读 36,576评论 2赞 327
白月光启示录
正文我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
茶点故事阅读 38,712评论 1赞 341
活死人
序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
沈念sama阅读 34,389评论 4赞 332
日本核电站爆炸内幕
正文年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
茶点故事阅读 40,032评论 3赞 316
男人毒药：我在死后第九天来索命
文/蒙蒙一、第九天我趴在偏房一处隐蔽的房顶上张望。院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
开封第一讲书人阅读 30,798评论 0赞 21
一桩弑父案，背后竟有这般阴谋
文/苍兰香墨我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。一阵脚步声响...
开封第一讲书人阅读 32,026评论 1赞 266
情欲美人皮
我被黑心中介骗来泰国打工，没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。一个月前我还...
沈念sama阅读 46,473评论 2赞 360
代替公主和亲
正文我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
茶点故事阅读 43,606评论 2赞 350