👉day 16

300. 最长递增子序列

难度中等2745

给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。

子序列 是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。

注意子序列以及子串, 对于子序列, 只需要保证顺序就行, 而子串需要保证连续

dp数组含义, : dp[i] 代表以nums[i] 结尾时, 数组的最长递增子序列
状态转移: 我们从当前的数组往前遍历 , 当遇到了比当前的num[i] 小的数时, 那么dp[i]=Math.max(dp[i],dp[j]+1)
dp数组初始化 : 由于每一个子序列至少含有一个元素, 因此dp数组的所有元素都应该初始化为 1
遍历方向以及范围: 从左向右顺序遍历 , 范围就是dp数组的所有数字
返回值 : 在遍历的过程中, 维护res , 每次都取最大值, 最后返回 , 记为最长递增子序列

class Solution {
    public int lengthOfLIS(int[] nums) {
        if(nums.length==1) return 1;
        int res=0;
        int[]dp=new int[nums.length]; //dp[i]表示 以nums[i]结尾的最长的递增的子序列的长度
        
        Arrays.fill(dp,1); // 初始化为 1
        for (int i = 0; i < nums.length; i++) {
            for (int j = i-1 ; j >= 0; j--) { 
                if(nums[i]>nums[j]){ // 注意不能执行完了一次if就直接跳出循环了, 因为元素的顺序与子序列的长度没关系
                    dp[i]=Math.max(dp[i],dp[j]+1);
                }
            }
            res=Math.max(res,dp[i]);
        }
        return res;
    }
}

673. 最长递增子序列的个数

难度中等651

给定一个未排序的整数数组 nums ， 返回最长递增子序列的个数 。

注意这个数列必须是严格递增的。

👉day 17

🎈1143. 最长公共子序列

labuladong 题解思路

难度中等1102

给定两个字符串 text1 和 text2，返回这两个字符串的最长 公共子序列 的长度。如果不存在 公共子序列 ，返回 0 。

一个字符串的 子序列 是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。

例如，"ace" 是 "abcde" 的子序列，但 "aec" 不是 "abcde" 的子序列。

两个字符串的 公共子序列 是这两个字符串所共同拥有的子序列。

小套路:

单个数组或者字符串要用动态规划时，可以把动态规划 dp[i] 定义为 nums[0:i] 中想要求的结果；

当两个数组或者字符串要用动态规划时，可以把动态规划定义成两维的 dp[i][j] ，其含义是在 A[0:i] 与 B[0:j] 之间匹配得到的想要的结果。

动态规划步骤:

dp数组定义: 本题是两个字符串, 那么优先采用二维数组, dp[i][j] 表示的是第一个字符串的[0:i] 与第二个字符串的[0:j的最长公共子序列
状态转移:
- 当s1[i]与s2[j] 相等时, 说明两个子串的最后一位相等, 此时最长公共子序列+1 dp[i][j]=dp[i-1][j-1]+1
- 如果当前的两个字符不相同, 那么当前的dp数组的值根据之前的值得出, dp[i][j]=Math.max(dp[i-1][j],dp[i][j-1])
状态的初始化 : 初始化也就是看 i=0 或者,j=0 的时候,dp[i][j]取多少,
- 当 i = 0 时，dp[0][j] 表示的是 text1 中取空字符串跟 text2 的最长公共子序列，结果肯定为 0.
- 当 j = 0 时，dp[i][0] 表示的是 text2 中取空字符串跟text1 的最长公共子序列，结果肯定为 0
遍历方向与范围:
- 遍历方向: 顺序遍历
- 范围, 注意dp数组的大小是new int[s1.length+1][s2.length+1] , 由于 i=0, j=0已经初始化, 所以直接从 i=1 ,j=1开始遍历, 遍历应该在遍历完字符串的时候结束, 也就是 i<=s1.length ;j<s2.length
最终返回结果: 结合dp数组的含义 ,最终返回 dp[s1.length][s2.length]

代码如下

class Solution {
    public int longestCommonSubsequence(String text1, String text2) {
        char[]s1=text1.toCharArray();
        char[]s2=text2.toCharArray();
        // dp[i] 表示的是 前i 项中 公共子序列的长度
        int len=Math.max(s1.length,s2.length);
        int [][]dp=new int[s1.length+1][s2.length+1];
        dp[0][0]=0; // 空字符串 , 序列都为0 ,因此初始化为0
        for (int i = 1; i <= s1.length; i++) {
            for (int j = 1; j <= s2.length; j++) {
                if(s1[i-1]==s2[j-1]){
                    dp[i][j]=dp[i-1][j-1]+1;
                }else{
                    dp[i][j]=Math.max(dp[i][j-1],dp[i-1][j]); // 左边的位置或者是上边的位置取最大的值
                }
            }
        }
        return dp[s1.length][s2.length];
    }
}

🎈718. 最长重复子数组

难度中等785

给两个整数数组 nums1 和 nums2 ，返回 两个数组中 公共的 、长度最长的子数组的长度 。

本题与上一题:🎈1143. 最长公共子序列几乎一模一样,
- 区别在于上一题是子序列, 本题需要的是子数组

注意子序列默认不连续, 子数组默认连续

那么本题主要解决的问题就是子数组连续的问题

其实解决这个问题看起来难 , 实施起来只需要稍加改动

dp思路

参考上一题

本题做出的改动:

状态转移部分:
- 上一题是 :
  - 当s1[i]与s2[j] 相等时, 说明两个子串的最后一位相等, 此时最长公共子序列+1 dp[i][j]=dp[i-1][j-1]+1
  - 如果当前的两个字符不相同, 那么当前的dp数组的值根据之前的值得出, dp[i][j]=Math.max(dp[i-1][j],dp[i][j-1])
- 本题 : 由于子数组要求连续, 因此只有在当前的两个元素相等的时候, 我们才可以进行状态转移 , 状态转移方程为:
  - dp[i][j]=dp[i-1][j-1]+1;

代码如下

class Solution {
    public int findLength(int[] nums1, int[] nums2) {
        int res=0;
        int[][]dp=new int[nums1.length+1][nums2.length+1];
        for (int i = 1; i < dp.length; i++) {
            for (int j = 1; j < dp[0].length; j++) {
                if(nums1[i-1]==nums2[j-1]){
                    dp[i][j]=dp[i-1][j-1]+1;
                }
                res=Math.max(res,dp[i][j]);
            }
        }
        return res;
    }
}

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

labuladong 题解思路

难度中等488

给定两个单词 word1 和 word2 ，返回使得 word1 和 word2 相同所需的最小步数。

每步可以删除任意一个字符串中的一个字符。

动态规划步骤:

dp数组定义: 本题是两个字符串, 那么优先采用二维数组, dp[i][j]表示 word1以i-1结尾出现的word2以j-1 结尾达到相同需要删除的次数
状态转移:
- 当w1[i]与w2[j] 相等时, 此时不需要删除任何字符 dp[i][j]=dp[i-1][j-1]
- 如果当前的两个字符不相同, 那么当前的dp数组的值根据之前的值得出
  1. 删除w2[j-1] 对应的方程就是 dp[i][j]=dp[i][j-1]+1;
  2. 删除w1[i-1] 对应的方程就是 dp[i][j]=dp[i-1][j]+1;
  3. 同时删除w1[i-1] w2[j-1] 对应的方程就是 dp[i][j]=dp[i-1][j-1]+2;
  那么当然是选最小值删除, 因此递推公式为:
  
  dp[i][j]=Math.min(Math.min(dp[i-1][j]+1,dp[i-1][j-1]+2),dp[i][j-1]+1);
状态的初始化 : 初始化也就是看 i=0 或者,j=0 的时候,dp[i][j]取多少,
- 当 i = 0 时，dp[i][0] i一个字符到空串需要删除i次
- 当 j = 0 时，dp[0][j] j个字符到空串需要删除j次
遍历方向与范围:
- 遍历方向: 顺序遍历
- 范围, 注意dp数组的大小是new int[s1.length+1][s2.length+1] , 由于 i=0, j=0已经初始化, 所以直接从 i=1 ,j=1开始遍历, 遍历应该在遍历完字符串的时候结束, 也就是 i<=s1.length ;j<s2.length
最终返回结果: 结合dp数组的含义 ,最终返回 dp[w1.length][w2.length]

代码如下

class Solution {
    public int minDistance(String word1, String word2) {
        int[][]dp=new int[word1.length()+1][word2.length()+1]; 
        // dp[i][j]表示  word1以i-1结尾出现的word2以j-1 结尾 达到相同 需要删除的最小次数
        char[]w1=word1.toCharArray();
        char[]w2=word2.toCharArray();
        for (int i = 0; i < dp.length; i++) { //初始化    i一个字符到空串需要删除i次
            dp[i][0]=i;
        }
        for (int j = 0; j < dp[0].length; j++) {//初始化   j个字符到空串需要删除j次
            dp[0][j]=j; 
        }
        for (int i = 1; i < dp.length; i++) {//bagg  bag
            for (int j = 1; j < dp[i].length; j++) {
                if(w1[i-1]==w2[j-1]){ // 两个相同, 不需要删除
                    dp[i][j]=dp[i-1][j-1];
                }else{ // 不相同 , 需要删除当前的字符  可以删除 w1[i-1][j]  w2[i][j-1]  或者都删除 =>dp[i][j]=dp[i-1][j-1]+2
                    dp[i][j]=Math.min(Math.min(dp[i-1][j]+1,dp[i-1][j-1]+2),dp[i][j-1]+1);
                }
            }
        }
        return dp[w1.length][w2.length];
    }
}

👉day 18

72. 编辑距离

labuladong 题解思路

难度困难2576

给你两个单词 word1 和 word2， 请返回将 word1 转换成 word2 所使用的最少操作数 。

你可以对一个单词进行如下三种操作：

插入一个字符
删除一个字符
替换一个字符

本题与前面的583. 两个字符串的删除操作非常类似

除了一点思路之外代码与动态规划步骤相差无几

动态规划步骤:

dp数组定义: 本题是两个字符串, 那么优先采用二维数组, dp[i][j]表示 word1以i-1结尾出现的word2以j-1 结尾达到相同需要删除的次数
状态转移:
- 当w1[i]与w2[j] 相等时, 此时不需要删除任何字符 dp[i][j]=dp[i-1][j-1]
- 如果当前的两个字符不相同, 那么当前的dp数组的值根据之前的值得出
  1. 删除w1[i-1] 对应的方程就是 dp[i][j]=dp[i-1][j]+1;
  2. 删除w2[j-1] 对应的方程就是 dp[i][j]=dp[i][j-1]+1;
  3. 替换元素, 直接把w1 或者 w2 的当前的元素替换, 使其与另一个元素相同, 此时不需要添加或者删除元素, 操作数就是dp[i][j]+1
  那么当然是选最小值删除, 因此递推公式为:
  
  dp[i][j]=Math.min(dp[i-1][j-1],Math.min(dp[i-1][j],dp[i][j-1]))+1;
为什么这里都是删除元素, 没有添加元素呢?
- word2删除一个元素, 就相当于word1添加一个元素
举例
- word1=“ad” ,word2=“a” ,
- word1 删除’d’ 与 word2 增加’d’ , 最终的操作数是一样的
状态的初始化 : 初始化也就是看 i=0 或者,j=0 的时候,dp[i][j]取多少,
- 当 i = 0 时，dp[i][0] i个字符到空串需要删除i次
- 当 j = 0 时，dp[0][j] j个字符到空串需要删除j次
遍历方向与范围:
- 遍历方向: 顺序遍历
- 范围, 注意dp数组的大小是new int[w1.length+1][w2.length+1] ,
- 由于 i=0, j=0已经初始化, 所以直接从 i=1 ,j=1开始遍历, 遍历应该在遍历完字符串的时候结束, 也就是 i<=w1.length ;j<=w2.length
最终返回结果: 结合dp数组的含义 ,最终返回 dp[w1.length][w2.length]

class Solution {
    public int minDistance(String word1, String word2) {
        int[][]dp=new int[word1.length()+1][word2.length()+1]; //// dp[i][j]表示  word1以i-1结尾出现的word2以j-1 结尾 达到相同 需要删除的次数
        char[]w1=word1.toCharArray();
        char[]w2=word2.toCharArray();
        // 变成空串只能删除
        for (int i = 0; i < dp.length; i++) { //初始化 一个字符到空串需要删除一次 ,
            dp[i][0]=i;
        }
        for (int j = 0; j < dp[0].length; j++) {//初始化 一个字符到空串需要删除一次
            dp[0][j]=j;
        }
        for (int i = 1; i < dp.length; i++) {//bagg  bag
            for (int j = 1; j < dp[i].length; j++) {
                if(w1[i-1]==w2[j-1]){ // 两个相同, 不需要操作
                    dp[i][j]=dp[i-1][j-1];
                }else{ // 不相同 , 增/删/换  添加是相对的, w1添加,就相当于w2删除, 注意理解这一部分
                    dp[i][j]=Math.min(dp[i][j-1],Math.min(dp[i-1][j],dp[i-1][j-1]))+1;
                }
            }
        }
        return dp[w1.length][w2.length];
    }
}

322. 零钱兑换

labuladong 题解思路

难度中等2118

给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。

计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回 -1 。

你可以认为每种硬币的数量是无限的。

完全背包问题

1、确定 base case，显然目标金额 amount 为 0 时算法返回 0，因为不需要任何硬币就已经凑出目标金额了。

2、确定「状态」，也就是原问题和子问题中会变化的变量。由于硬币数量无限，硬币的面额也是题目给定的，只有目标金额会不断地向 base case 靠近，所以唯一的「状态」就是目标金额 amount。

3、确定初始化 , 凑成 amount 金额的数最多只可能等于 amount（全用 1 元面值的），所以初始化为 amount + 1 就相当于初始化为正无穷，便于后续取最小值。

4、确定「选择」，也就是导致「状态」产生变化的行为。目标金额为什么变化呢，因为你在选择硬币，你每选择一枚硬币，就相当于减少了目标金额。所以说所有硬币的面值，就是你的「选择」。

5、明确 dp 函数/数组的定义：输入一个目标金额 n，返回凑出目标金额 n 的最少硬币数量。

按照 dp 函数的定义描述「选择」，得到最终答案 dp(amount)。

class Solution {
    public int coinChange(int[] coins, int amount) { //先物品再背包
        int[]dp=new int[amount+1]; // dp[i] 表示集齐i value 需要的最小的硬币的数目
        Arrays.fill(dp,amount+1);
        dp[0]=0;
        // 本题 coins 的每个硬币的面额就相当于value ,  每个硬币的weight 都是1 , dp[i]的i 就相当于 bagWeight ,
        for (int i = 0; i < coins.length; i++) {
            for (int j = coins[i]; j <= amount; j++) {
                if(dp[j-coins[i]]!=amount+1){
                    dp[j]=Math.min(dp[j],dp[j-coins[i]]+1);
                }
            }
        }
        return dp[amount]==amount+1?-1:dp[amount];
    }

}

343. 整数拆分

难度中等923

给定一个正整数 n ，将其拆分为 k 个 正整数 的和（ k >= 2 ），并使这些整数的乘积最大化。

返回 你可以获得的最大乘积 。

本题的数学定理 , 对于每一项, 拆分成 3 可以使乘积最大
对于 4 , 拆分成 2*2 最大(也可以直接*4)

代码如下

class Solution {
    public int integerBreak(int n) {
        if(n<=3 )return n-1;
        int res=1;
        while(n>4){
            n-=3;
            res*=3;
        }
        return n*res;
    }
}

😈其他题目

91. 解码方法

思路

难度中等1239

一条包含字母 A-Z 的消息通过以下映射进行了编码：

'A' -> "1"
'B' -> "2"
...
'Z' -> "26"

要解码已编码的消息，所有数字必须基于上述映射的方法，反向映射回字母（可能有多种方法）。例如，"11106" 可以映射为：

"AAJF" ，将消息分组为 (1 1 10 6)
"KJF" ，将消息分组为 (11 10 6)

注意，消息不能分组为 (1 11 06) ，因为 "06" 不能映射为 "F" ，这是由于 "6" 和 "06" 在映射中并不等价。

给你一个只含数字的非空字符串 s ，请计算并返回解码方法的总数。

题目数据保证答案肯定是一个 32 位 的整数。

暴力

class Solution {
    public int numDecodings(String s) {
        if(s.length()==0) return 0;
        return process(s.toCharArray(),0);
    }

    /** str[0...i-1]已经转换完了,固定了
     i以后有几种转换的结果
     'A' -> "1"
     'B' -> "2"
     ...
     'Z' -> "26"
     */
    public int process(char[]chars,int i){
        if(i==chars.length) return 1; // 没有字符了,  只有一种转化情况 就是0~i-1 转换的结果
        if(chars[i]==0x30) return 0; //0  不能转换
        if(chars[i]==0x31){
            int res=process(chars,i+1);
            if(i+1<chars.length){
                res+=process(chars,i+2);// i ,i+1 合并转换为一个字符 , 再加上后续的转换的方法的数量
            }
            return res;
        }else if(chars[i]==0x32){
            int res=process(chars,i+1);
            if(i+1<chars.length&&chars[i+1]<=0x36){
                res+=process(chars,i+2);// i ,i+1 合并转换为一个字符 , 再加上后续的转换的方法的数量
            }
            return res;
        }
        return process(chars,i+1);
    }
}

思路类似于斐波那契数列, 注意需要考虑情况

class Solution {
    public int numDecodings(String s) {
        if(s.length()==0) return 0;
        char[]chars=s.toCharArray();
        int pre=1,cur=1; // dp[-1]=dp[0]=1
        for(int i=1;i<s.length();i++){
            int tmp=cur;
            if(chars[i]==0x30){
                if(chars[i-1]==0x31||chars[i-1]==0x32){
                    cur=pre;
                }else{
                    return 0;
                }
            }
            else if(chars[i-1]==0x31||(chars[i-1]==0x32&&chars[i]<=0x36)){
                cur+=pre;
            }
            pre=tmp;
        }
        return cur;
    }
}

115. 不同的子序列

labuladong 题解思路

难度困难862

给定一个字符串 s 和一个字符串 t ，计算在 s 的子序列中 t 出现的个数。

字符串的一个 子序列 是指，通过删除一些（也可以不删除）字符且不干扰剩余字符相对位置所组成的新字符串。（例如，"ACE" 是 "ABCDE" 的一个子序列，而 "AEC" 不是）

题目数据保证答案符合 32 位带符号整数范围。

动态规划步骤:

dp数组定义: 本题是两个字符串, 那么优先采用二维数组, dp[i][j] 表示 s以i-1结尾出现的 t以j-1 结尾的子序列的个数
状态转移:
- 当s1[i]与s2[j] 相等时, 说明两个子串的最后一位相等, 此时最长公共子序列+1 dp[i][j]=dp[i-1][j-1]+1
- 如果当前的两个字符不相同, 那么当前的dp数组的值根据之前的值得出, dp[i][j]=Math.max(dp[i-1][j],dp[i][j-1])
状态的初始化 : 初始化也就是看 i=0 或者,j=0 的时候,dp[i][j]取多少,
- 当 i = 0 时，dp[0][j] 表示的是 text1 中取空字符串跟 text2 的最长公共子序列，结果肯定为 0.
- 当 j = 0 时，dp[i][0] 表示的是 text2 中取空字符串跟text1 的最长公共子序列，结果肯定为 0
遍历方向与范围:
- 遍历方向: 顺序遍历
- 范围, 注意dp数组的大小是new int[s1.length+1][s2.length+1] , 由于 i=0, j=0已经初始化, 所以直接从 i=1 ,j=1开始遍历, 遍历应该在遍历完字符串的时候结束, 也就是 i<=s1.length ;j<s2.length
最终返回结果: 结合dp数组的含义 ,最终返回 dp[s1.length][s2.length]

class Solution {
    public int numDistinct(String s, String t) {
        int[][]dp=new int[s.length()+1][t.length()+1]; // Dp[i][j]表示  s以i-1结尾出现的 t以j-1 结尾的子序列的个数
        // 初始化为 0,
        char[]s1=s.toCharArray();
        char[]t1=t.toCharArray();
        for (int i = 0; i < dp.length; i++) { // t为空串的时候, i=1 此时的s只需要删除一个字符就可以变成 t
            dp[i][0]=1;
        }
        for (int i = 1; i < dp.length; i++) { // baegsg  bag
            for (int j = 1; j < dp[0].length; j++) {
                if(s1[i-1]==t1[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()];
    }
}