动态算法

动态规划

62 不同路径

62. 不同路径

难度中等1446

一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。

机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。

问总共有多少条不同的路径？

示例 1：

输入：m = 3, n = 7
输出：28

示例 2：

输入：m = 3, n = 2
输出：3
解释：
从左上角开始，总共有 3 条路径可以到达右下角。
1. 向右 -> 向下 -> 向下
2. 向下 -> 向下 -> 向右
3. 向下 -> 向右 -> 向下

示例 3：

输入：m = 7, n = 3
输出：28

示例 4：

输入：m = 3, n = 3
输出：6

解答

class Solution {
    public int uniquePaths(int m, int n) {
        int dp[][]=new int[m][n];
       for(int i=0;i<n;i++){
            dp[0][i]=1;
        }
        for(int i=0;i<m;i++){
            dp[i][0]=1;
        }

        for(int i=1;i<m;i++){
            for(int j=1;j<n;j++){
                dp[i][j]=dp[i-1][j]+dp[i][j-1];
            }
        }
        return dp[m-1][n-1];
    }
}

343 整数拆分

343. 整数拆分

难度中等854

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

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

示例 1:

输入: n = 2
输出: 1
解释: 2 = 1 + 1, 1 × 1 = 1。

示例 2:

输入: n = 10
输出: 36
解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36

class Solution {
    public int integerBreak(int n) {
        int []dp=new int[n+1];
        dp[2]=1;
        for(int i=3;i<=n;i++){
            for(int j=1;j<=i-j;j++){
                dp[i]=Math.max(dp[i],Math.max(j*(i-j),j*dp[i-j]));
            }
        }
        return dp[n];
    }
}

背包问题

重点把握01背包和完全背包

可以用二维数组或者一维数组来解决背包问题

题目：

在下面的讲解中，我举一个例子：

背包最大重量为4。

物品为：

	重量	价值
物品0	1	15
物品1	3	20
物品2	4	30

问背包能背的物品最大价值是多少？

//二维数组
//dp[i][j] 的含义  在i-1个物品中选择   容量为j  的最大价值
//递推公式  dp[i][j]=Math.max(dp[i-1][j],dp[i-1][j-weight[i]]+value[i])

public static void main(String[] args) {
        int[] weight = {1, 3, 4};
        int[] value = {15, 20, 30};
        int bagsize = 4;
        testweightbagproblem(weight, value, bagsize);
    }

    public static void testweightbagproblem(int[] weight, int[] value, int bagsize){
        int wlen = weight.length, value0 = 0;
        //定义dp数组：dp[i][j]表示背包容量为j时，前i个物品能获得的最大价值
        int[][] dp = new int[wlen + 1][bagsize + 1];
        //初始化：背包容量为0时，能获得的价值都为0
        for (int i = 0; i <= wlen; i++){
            dp[i][0] = value0;
        }
        //遍历顺序：先遍历物品，再遍历背包容量
        for (int i = 1; i <= wlen; i++){
            for (int j = 1; j <= bagsize; j++){
                if (j < weight[i - 1]){
                    dp[i][j] = dp[i - 1][j];
                }else{
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - weight[i - 1]] + value[i - 1]);
                }
            }
        }
        //打印dp数组
        for (int i = 0; i <= wlen; i++){
            for (int j = 0; j <= bagsize; j++){
                System.out.print(dp[i][j] + " ");
            }
            System.out.print("\n");
        }
    }

解答二 一维数组来解决背包问题

//一维数组  dp[j]  在容量为j的情况下  所获得的最大价值
//递推公式   dp[j]=Math.max(dp[j],dp[j-weight[i]]+value[i])

//遍历顺序
for(int i = 0; i < weight.size(); i++) { // 遍历物品
    for(int j = bagWeight; j >= weight[i]; j--) { // 遍历背包容量
        dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);

    }
}

倒序遍历是为了保证物品i只被放入一次！。但如果一旦正序遍历了，那么物品0就会被重复加入多次！
举一个例子：物品0的重量weight[0] = 1，价值value[0] = 15
如果正序遍历
dp[1] = dp[1 - weight[0]] + value[0] = 15
dp[2] = dp[2 - weight[0]] + value[0] = 30
此时dp[2]就已经是30了，意味着物品0，被放入了两次，所以不能正序遍历。
为什么倒序遍历，就可以保证物品只放入一次呢？
倒序就是先算dp[2]
dp[2] = dp[2 - weight[0]] + value[0] = 15 （dp数组已经都初始化为0）
dp[1] = dp[1 - weight[0]] + value[0] = 15

所以从后往前循环，每次取得状态不会和之前取得状态重合，这样每种物品就只取一次了。

那么问题又来了，为什么二维dp数组历的时候不用倒序呢？

因为对于二维dp，dp[i][j]都是通过上一层即dp[i - 1][j]计算而来，本层的dp[i][j]并不会被覆盖！

（如何这里读不懂，大家就要动手试一试了，空想还是不靠谱的，实践出真知！）

//再来看看两个嵌套for循环的顺序，代码中是先遍历物品嵌套遍历背包容量，那可不可以先遍历背包容量嵌套遍历物品呢？

不可以！

因为一维dp的写法，背包容量一定是要倒序遍历（原因上面已经讲了），如果遍历背包容量放在上一层，那么每个dp[j]就只会放入一个物品，即：背包里只放入了一个物品。

倒序遍历的原因是，本质上还是一个对二维数组的遍历，并且右下角的值依赖上一层左上角的值，因此需要保证左边的值仍然是上一层的，从右向左覆盖。

（这里如果读不懂，就在回想一下dp[j]的定义，或者就把两个for循环顺序颠倒一下试试！）

所以一维dp数组的背包在遍历顺序上和二维其实是有很大差异的！

   public static void main(String[] args) {
        int[] weight = {1, 3, 4};
        int[] value = {15, 20, 30};
        int bagWight = 4;
        testWeightBagProblem(weight, value, bagWight);
    }

    public static void testWeightBagProblem(int[] weight, int[] value, int bagWeight){
        int wLen = weight.length;
        //定义dp数组：dp[j]表示背包容量为j时，能获得的最大价值
        int[] dp = new int[bagWeight + 1];
        //遍历顺序：先遍历物品，再遍历背包容量
        for (int i = 0; i < wLen; i++){
            for (int j = bagWeight; j >= weight[i]; j--){
                dp[j] = Math.max(dp[j], dp[j - weight[i]] + value[i]);
            }
        }
        //打印dp数组
        for (int j = 0; j <= bagWeight; j++){
            System.out.print(dp[j] + " ");
        }
    }

416 分割等和子集

416. 分割等和子集

难度中等1413

给你一个 只包含正整数 的 非空 数组 nums 。请你判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。

示例 1：

输入：nums = [1,5,11,5]
输出：true
解释：数组可以分割成 [1, 5, 5] 和 [11] 。

示例 2：

输入：nums = [1,2,3,5]
输出：false
解释：数组不能分割成两个元素和相等的子集。 

提示：

• 1 <= nums.length <= 200
• 1 <= nums[i] <= 100

解答

 class Solution {
    public boolean canPartition(int[] nums) {
          if(nums.length<2){
              return false;
          }
          int sum=0;
          for(int x:nums){
              sum+=x;
          }

          if(sum%2==1){
              return false;
          }
        //目标为  sum/2
          int target=sum/2;
          int []dp=new int[target+1];

          for(int i=0;i<nums.length;i++){
              for(int j=target;j>=nums[i];j--){
                  dp[j]=Math.max(dp[j],dp[j-nums[i]]+nums[i]);
              }
          }

          return  dp[target]==target;
    }
}

1049 最后一块石头的重量 2

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

难度中等505

有一堆石头，用整数数组 stones 表示。其中 stones[i] 表示第 i 块石头的重量。

每一回合，从中选出任意两块石头，然后将它们一起粉碎。假设石头的重量分别为 x 和 y，且 x <= y。那么粉碎的可能结果如下：

• 如果 x == y，那么两块石头都会被完全粉碎；
• 如果 x != y，那么重量为 x 的石头将会完全粉碎，而重量为 y 的石头新重量为 y-x。

最后，最多只会剩下一块 石头。返回此石头 最小的可能重量 。如果没有石头剩下，就返回 0。

示例 1：

输入：stones = [2,7,4,1,8,1]
输出：1
解释：
组合 2 和 4，得到 2，所以数组转化为 [2,7,1,8,1]，
组合 7 和 8，得到 1，所以数组转化为 [2,1,1,1]，
组合 2 和 1，得到 1，所以数组转化为 [1,1,1]，
组合 1 和 1，得到 0，所以数组转化为 [1]，这就是最优值。

示例 2：

输入：stones = [31,26,33,21,40]
输出：5

解答

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

        return sum-2*dp[target];
    }
}

494 目标和

494. 目标和

难度中等1316

给你一个整数数组 nums 和一个整数 target 。

向数组中的每个整数前添加 '+' 或 '-' ，然后串联起所有整数，可以构造一个 表达式 ：

• 例如，nums = [2, 1] ，可以在 2 之前添加 '+' ，在 1 之前添加 '-' ，然后串联起来得到表达式 "+2-1" 。

返回可以通过上述方法构造的、运算结果等于 target 的不同 表达式 的数目。

示例 1：

输入：nums = [1,1,1,1,1], target = 3
输出：5
解释：一共有 5 种方法让最终目标和为 3 。
-1 + 1 + 1 + 1 + 1 = 3
+1 - 1 + 1 + 1 + 1 = 3
+1 + 1 - 1 + 1 + 1 = 3
+1 + 1 + 1 - 1 + 1 = 3
+1 + 1 + 1 + 1 - 1 = 3

示例 2：

输入：nums = [1], target = 1
输出：1

解答

class Solution {
    public int findTargetSumWays(int[] nums, int target) {
        int sum=0;
        for (int num : nums) {
            sum+=num;
        }
        if((sum+target)%2==1){
            return 0;
        }

        int size=(sum+target)/2;
        if(size<0){
            size=-1*size;
        }

        int []dp=new int[size+1];
        dp[0]=1;
        for (int i = 0; i <nums.length ; i++) {
            for (int j = size; j >=nums[i] ; j--) {
                dp[j]+=dp[j-nums[i]];
            }
        }

        return  dp[size];
    }
}

解答二 回溯

public static int res=0;
    
    public  static  int findTargetSumWays(int[] nums, int target) {
        int index=0;//遍历索引
        int temp=0; //累加结果
        backTrack(nums,target,temp,index);
       return  res;
    }

    private static void backTrack(int[] nums, int target,  int temp,int index) {
        if(index==nums.length){
            if(temp==target){
                res++;
            }
        }else{
            backTrack(nums,target,temp-nums[index],index+1);
            backTrack(nums,target,temp+nums[index],index+1);
        }
    }
    

474 1和0

474. 一和零

难度中等767

给你一个二进制字符串数组 strs 和两个整数 m 和 n 。

请你找出并返回 strs 的最大子集的长度，该子集中 最多 有 m 个 0 和 n 个 1 。

如果 x 的所有元素也是 y 的元素，集合 x 是集合 y 的 子集 。

示例 1：

输入：strs = ["10", "0001", "111001", "1", "0"], m = 5, n = 3
输出：4
解释：最多有 5 个 0 和 3 个 1 的最大子集是 {"10","0001","1","0"} ，因此答案是 4 。
其他满足题意但较小的子集包括 {"0001","1"} 和 {"10","1","0"} 。{"111001"} 不满足题意，因为它含 4 个 1 ，大于 n 的值 3 。

示例 2：

输入：strs = ["10", "0", "1"], m = 1, n = 1
输出：2
解释：最大的子集是 {"0", "1"} ，所以答案是 2 。

提示：

• 1 <= strs.length <= 600
• 1 <= strs[i].length <= 100
• strs[i] 仅由 '0' 和 '1' 组成
• 1 <= m, n <= 100

解答

class Solution {
    public int findMaxForm(String[] strs, int m, int n) {
          int [][]dp=new int[m+1][n+1];
         for (String s : strs) {
            int zero=0;
            int one=0;
            char[] chars = s.toCharArray();

            for (int i = 0; i < chars.length; i++) {
                if(chars[i]=='0'){
                    zero++;
                }else{
                    one++;
                }
            }
            for (int i = m; i >=zero ; i--) {
                for (int j = n; j >=one ; j--) {
                    dp[i][j]=Math.max(dp[i][j],dp[i-zero][j-one]+1);
                }
            }


        }
        return dp[m][n];

    }
}

518 零钱兑换2

518. 零钱兑换 II

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

请你计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额，返回 0 。

假设每一种面额的硬币有无限个。

题目数据保证结果符合 32 位带符号整数。

示例 1：

输入：amount = 5, coins = [1, 2, 5]
输出：4
解释：有四种方式可以凑成总金额：
5=5
5=2+2+1
5=2+1+1+1
5=1+1+1+1+1

示例 2：

输入：amount = 3, coins = [2]
输出：0
解释：只用面额 2 的硬币不能凑成总金额 3 。

示例 3：

输入：amount = 10, coins = [10] 
输出：1 

提示：

• 1 <= coins.length <= 300
• 1 <= coins[i] <= 5000
• coins 中的所有值 互不相同
• 0 <= amount <= 5000

解答 （完全背包）

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

377 组合总和IV

377. 组合总和 Ⅳ

难度中等675收藏分享切换为英文接收动态反馈

给你一个由 不同 整数组成的数组 nums ，和一个目标整数 target 。请你从 nums 中找出并返回总和为 target 的元素组合的个数。

示例 1：

输入：nums = [1,2,3], target = 4
输出：7
解释：
所有可能的组合为：
(1, 1, 1, 1)
(1, 1, 2)
(1, 2, 1)
(1, 3)
(2, 1, 1)
(2, 2)
(3, 1)
请注意，顺序不同的序列被视作不同的组合。

示例 2：

输入：nums = [9], target = 3
输出：0 

提示：

• 1 <= nums.length <= 200
• 1 <= nums[i] <= 1000
• nums 中的所有元素 互不相同
• 1 <= target <= 1000

解答

/**
完全背包问题
这道题目求的是排列总数  
所以要先遍历背包
再遍历物品
**/
class Solution {
    public int combinationSum4(int[] nums, int target) {
        int []dp=new int[target+1];
        dp[0]=1;

        for (int i = 1; i <=target ; i++) {
            for (int j = 0; j <nums.length ; j++) {
                if(i>=nums[j]) {
                    dp[i] += dp[i - nums[j]];
                }
            }
        }
        return dp[target];
    }
}

322 零钱兑换

322. 零钱兑换

难度中等2062收藏分享切换为英文接收动态反馈

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

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

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

示例 1：

输入：coins = [1, 2, 5], amount = 11
输出：3 
解释：11 = 5 + 5 + 1

示例 2：

输入：coins = [2], amount = 3
输出：-1

示例 3：

输入：coins = [1], amount = 0
输出：0 

提示：

• 1 <= coins.length <= 12
• 1 <= coins[i] <= 231 - 1
• 0 <= amount <= 104

解答

class Solution {
    public int coinChange(int[] coins, int amount) {
        int max = Integer.MAX_VALUE;
        int []dp=new int[amount+1];
        for (int i = 0; i < dp.length; i++) {
            dp[i]=max;
        }
        dp[0]=0;
        for (int i = 0; i < coins.length; i++) {
            for (int j = coins[i]; j <=amount ; j++) {
                //必须要加  因为有一种情况  该硬币无法组成  比如[2] 3 如果不加的话dp[3]=dp[1]+1  dp[1]=Integer.MAX_VALUE  直接爆了  另外加的话可以筛选不满足条件
                if (dp[j - coins[i]] != max) {
                    dp[j] = Math.min(dp[j], dp[j - coins[i]] + 1);
                }
            }
        }
       return dp[amount] == max ? -1 : dp[amount];
    }
}

279 完全平方数

279. 完全平方数](https://leetcode.cn/problems/perfect-squares/)

给你一个整数 n ，返回 和为 n 的完全平方数的最少数量 。

完全平方数 是一个整数，其值等于另一个整数的平方；换句话说，其值等于一个整数自乘的积。例如，1、4、9 和 16 都是完全平方数，而 3 和 11 不是。

示例 1：

输入：n = 12
输出：3 
解释：12 = 4 + 4 + 4

示例 2：

输入：n = 13
输出：2
解释：13 = 4 + 9

提示：

• 1 <= n <= 104

解答

class Solution {
    public int numSquares(int n) {
       int max=Integer.MAX_VALUE;
        int []dp=new int[n+1];
        for (int i = 0; i < dp.length; i++) {
            dp[i]=max;
        }
        dp[0]=0;
        dp[1]=1;
        for (int i = 1; i <=n ; i++) {
            for (int j = i*i; j <=n ; j++) {
                //这行代码加不加都可以  因为每个数  必定会有一个结果 就是由n个1组成  
                if(dp[j-i*i]!=max) {
                    dp[j] = Math.min(dp[j], dp[j - i * i] + 1);
                }
            }
        }
        return dp[n];
    }
}

139 单词拆分

139. 单词拆分

给你一个字符串 s 和一个字符串列表 wordDict 作为字典。请你判断是否可以利用字典中出现的单词拼接出 s 。

注意：不要求字典中出现的单词全部都使用，并且字典中的单词可以重复使用。

示例 1：

输入: s = "leetcode", wordDict = ["leet", "code"]
输出: true
解释: 返回 true 因为 "leetcode" 可以由 "leet" 和 "code" 拼接成。

示例 2：

输入: s = "applepenapple", wordDict = ["apple", "pen"]
输出: true
解释: 返回 true 因为 "applepenapple" 可以由 "apple" "pen" "apple" 拼接成。
注意，你可以重复使用字典中的单词。

示例 3：

输入: s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"]
输出: false

解答 回溯 超时

class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        StringBuilder str=new StringBuilder();
        ArrayList<Integer> list = new ArrayList<>();
        int res=0;
        backTrack(s, wordDict, str,list);
        return list.size()>0;
    }

     private static void backTrack(String s, List<String> wordDict, StringBuilder str,ArrayList<Integer> list) {
        if(str.toString().length()>s.length()){
            return;
        }
        if(str.toString().length()==s.length() && !str.toString().equals(s) ){
            return;
        }
        if(str.toString().equals(s)){
            list.add(new Integer(1));
            return;
        }
        for (int i = 0; i < wordDict.size(); i++) {
            str.append(wordDict.get(i));
            backTrack(s,wordDict,str,list);
            str.delete(str.length()-wordDict.get(i).length(),str.length());
        }

    }
}

解答2

 public  static boolean wordBreak1(String s, List<String> wordDict) {
        boolean [] valid=new boolean[s.length()+1];
         valid[0]=true;
         //先遍历物品 在遍历背包
        for (int i = 1; i <=s.length() ; i++) {
            for (int j = 0; j <i ; j++) {
                if(wordDict.contains(s.substring(j,i)) && valid[j]){
                    valid[j]=true;
                }
            }
        }
        return valid[s.length()];

    }

198 打家劫舍

198. 打家劫舍

难度中等2228收藏分享切换为英文接收动态反馈

你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。

给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。

示例 1：

输入：[1,2,3,1]
输出：4
解释：偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。
偷窃到的最高金额 = 1 + 3 = 4 。

示例 2：

输入：[2,7,9,3,1]
输出：12
解释：偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9)，接着偷窃 5 号房屋 (金额 = 1)。
偷窃到的最高金额 = 2 + 9 + 1 = 12 。

解答

class Solution {
    public int rob(int[] nums) {
        if(nums.length==1){
            return nums[0];
        }

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

    }
}

213 打家劫舍2

213. 打家劫舍 II](https://leetcode.cn/problems/house-robber-ii/)

难度中等1112收藏分享切换为英文接收动态反馈

你是一个专业的小偷，计划偷窃沿街的房屋，每间房内都藏有一定的现金。这个地方所有的房屋都 围成一圈 ，这意味着第一个房屋和最后一个房屋是紧挨着的。同时，相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警 。

给定一个代表每个房屋存放金额的非负整数数组，计算你 在不触动警报装置的情况下 ，今晚能够偷窃到的最高金额。

示例 1：

输入：nums = [2,3,2]
输出：3
解释：你不能先偷窃 1 号房屋（金额 = 2），然后偷窃 3 号房屋（金额 = 2）, 因为他们是相邻的。

示例 2：

输入：nums = [1,2,3,1]
输出：4
解释：你可以先偷窃 1 号房屋（金额 = 1），然后偷窃 3 号房屋（金额 = 3）。
偷窃到的最高金额 = 1 + 3 = 4 。

示例 3：

输入：nums = [1,2,3]
输出：3

解答 分区间讨论

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 res1 = method(nums, 0, nums.length - 2);
         int res2 = method(nums, 1, nums.length - 1);
         return Math.max(res1,res2);

    }

     public static int method(int[] nums,int left,int right) {
       int []dp=new int[nums.length];
       dp[left]=nums[left];
       dp[left+1]=Math.max(nums[left],nums[left+1]);
        for (int i = left+2; i <=right ; i++) {
                dp[i]=Math.max(dp[i-2]+nums[i],dp[i-1]);
        }
       return  dp[right];
    }
}

121. 买卖股票的最佳时机

121. 买卖股票的最佳时机

难度简单2472收藏分享切换为英文接收动态反馈

给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。

你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。

返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。

示例 1：

输入：[7,1,5,3,6,4]
输出：5
解释：在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。
注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格；同时，你不能在买入前卖出股票。

示例 2：

输入：prices = [7,6,4,3,1]
输出：0
解释：在这种情况下, 没有交易完成, 所以最大利润为0。

提示：

• 1 <= prices.length <= 105
• 0 <= prices[i] <= 104

解答 暴力超时

 public static int maxProfit(int[] prices) {
         int []dp=new int[prices.length];
        for (int i = 1; i < prices.length; i++) {
            for (int j = 0; j <i ; j++) {
                dp[i]=Math.max(dp[i],prices[i]-prices[j]);
            }
        }
        Arrays.sort(dp);
        return dp[prices.length-1];
    }

解答2 动态规划

class Solution {
    public int maxProfit(int[] prices) {
        if(prices.length==1){
            return 0;
        }
         int [][]dp=new int[prices.length][2];
        // dp[i][0]代表第i天持有股票的最大收益
        // dp[i][1]代表第i天不持有股票的最大收益
        dp[0][0]=-prices[0];
        dp[0][1]=0;
        for (int i = 1; i < prices.length; i++) {
            dp[i][0]=Math.max(dp[i-1][0],-prices[i]);
            dp[i][1]=Math.max(dp[i-1][0]+prices[i],dp[i-1][1]);
        }
        return dp[prices.length-1][1];
    }
}

122 买卖股票的最佳时机2

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

难度中等1782收藏分享切换为英文接收动态反馈

给你一个整数数组 prices ，其中 prices[i] 表示某支股票第 i 天的价格。

在每一天，你可以决定是否购买和/或出售股票。你在任何时候 最多 只能持有 一股 股票。你也可以先购买，然后在 同一天 出售。

返回 你能获得的 最大 利润 。

示例 1：

输入：prices = [7,1,5,3,6,4]
输出：7
解释：在第 2 天（股票价格 = 1）的时候买入，在第 3 天（股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5 - 1 = 4 。
随后，在第 4 天（股票价格 = 3）的时候买入，在第 5 天（股票价格 = 6）的时候卖出, 这笔交易所能获得利润 = 6 - 3 = 3 。
总利润为 4 + 3 = 7 。

示例 2：

输入：prices = [1,2,3,4,5]
输出：4
解释：在第 1 天（股票价格 = 1）的时候买入，在第 5 天 （股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5 - 1 = 4 。
总利润为 4 。

示例 3：

输入：prices = [7,6,4,3,1]
输出：0
解释：在这种情况下, 交易无法获得正利润，所以不参与交易可以获得最大利润，最大利润为 0 。

提示：

• 1 <= prices.length <= 3 * 104
• 0 <= prices[i] <= 104

解答

class Solution {
    public int maxProfit(int[] prices) {
         if(prices.length==1){
            return 0;
        }
        int [][]dp=new int[prices.length][2];
        // dp[i][0]代表第i天持有股票的最大收益
        // dp[i][1]代表第i天不持有股票的最大收益
        dp[0][0]=-prices[0];
        dp[0][1]=0;
        for (int i = 1; i < prices.length; i++) {
            //只在这一句代码跟上一题不同
            dp[i][0]=Math.max(dp[i-1][0],dp[i-1][1]-prices[i]);
            dp[i][1]=Math.max(dp[i-1][0]+prices[i],dp[i-1][1]);
        }

        return dp[prices.length-1][1];

    }
}

123 买卖股票的最佳时机3

123. 买卖股票的最佳时机 III

难度困难1192收藏分享切换为英文接收动态反馈

给定一个数组，它的第 i 个元素是一支给定的股票在第 i 天的价格。

设计一个算法来计算你所能获取的最大利润。你最多可以完成 两笔 交易。

注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

示例 1:

输入：prices = [3,3,5,0,0,3,1,4]
输出：6
解释：在第 4 天（股票价格 = 0）的时候买入，在第 6 天（股票价格 = 3）的时候卖出，这笔交易所能获得利润 = 3-0 = 3 。
随后，在第 7 天（股票价格 = 1）的时候买入，在第 8 天 （股票价格 = 4）的时候卖出，这笔交易所能获得利润 = 4-1 = 3 。

示例 2：

输入：prices = [1,2,3,4,5]
输出：4
解释：在第 1 天（股票价格 = 1）的时候买入，在第 5 天 （股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。   
注意你不能在第 1 天和第 2 天接连购买股票，之后再将它们卖出。   
因为这样属于同时参与了多笔交易，你必须在再次购买前出售掉之前的股票。

示例 3：

输入：prices = [7,6,4,3,1] 
输出：0 
解释：在这个情况下, 没有交易完成, 所以最大利润为 0。

示例 4：

输入：prices = [1]
输出：0

解答

class Solution {
    public int maxProfit(int[] prices) {
       if(prices.length==1){
            return  0;
        }
        int [][]dp=new int[prices.length][5];
        dp[0][1]=-prices[0];
        dp[0][3]=-prices[0];
        for (int i = 1; i <prices.length ; i++) {
            dp[i][0]=dp[i-1][0];
            dp[i][1]=Math.max(dp[i-1][1],dp[i-1][0]-prices[i]);
            dp[i][2]=Math.max(dp[i-1][2],dp[i-1][1]+prices[i]);
            dp[i][3]=Math.max(dp[i-1][3],dp[i-1][2]-prices[i]);
            dp[i][4]=Math.max(dp[i-1][4],dp[i-1][3]+prices[i]);
        }
        return dp[prices.length - 1][4];

    }
}

188 买卖股票的最佳时机4

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

难度困难780收藏分享切换为英文接收动态反馈

给定一个整数数组 prices ，它的第 i 个元素 prices[i] 是一支给定的股票在第 i 天的价格。

设计一个算法来计算你所能获取的最大利润。你最多可以完成 k 笔交易。

注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

示例 1：

输入：k = 2, prices = [2,4,1]
输出：2
解释：在第 1 天 (股票价格 = 2) 的时候买入，在第 2 天 (股票价格 = 4) 的时候卖出，这笔交易所能获得利润 = 4-2 = 2 。

示例 2：

输入：k = 2, prices = [3,2,6,5,0,3]
输出：7
解释：在第 2 天 (股票价格 = 2) 的时候买入，在第 3 天 (股票价格 = 6) 的时候卖出, 这笔交易所能获得利润 = 6-2 = 4 。
随后，在第 5 天 (股票价格 = 0) 的时候买入，在第 6 天 (股票价格 = 3) 的时候卖出, 这笔交易所能获得利润 = 3-0 = 3 。

解答

class Solution {
    public int maxProfit(int k, int[] prices) {
        if(k==0 || prices.length==0 || prices.length==1){
            return 0;
        }
         int [][]dp=new int[prices.length][2*k+1];
        for (int i = 1; i < 2*k; i+=2) {
            dp[0][i]=-prices[0];
        }
        for (int i = 1; i <prices.length ; i++) {
            for (int j = 0; j < 2*k-1; j+=2) {
                dp[i][j+1]=Math.max(dp[i-1][j+1],dp[i-1][j]-prices[i]);
                dp[i][j+2]=Math.max(dp[i-1][j+2],dp[i-1][j+1]+prices[i]);
            }
        }

        return  dp[prices.length-1][2*k];

    }
}

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

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

难度中等1281收藏分享切换为英文接收动态反馈

给定一个整数数组prices，其中第 prices[i] 表示第 *i* 天的股票价格 。

设计一个算法计算出最大利润。在满足以下约束条件下，你可以尽可能地完成更多的交易（多次买卖一支股票）:

• 卖出股票后，你无法在第二天买入股票 (即冷冻期为 1 天)。

注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

示例 1:

输入: prices = [1,2,3,0,2]
输出: 3 
解释: 对应的交易状态为: [买入, 卖出, 冷冻期, 买入, 卖出]

示例 2:

输入: prices = [1]
输出: 0

解答

class Solution {
    public int maxProfit(int[] prices) {
        if (prices == null || prices.length < 2) {
            return 0;
        }
       int [][]dp=new int[prices.length][4];
        dp[0][0]=-prices[0];
        for (int i = 1; i < prices.length; i++) {
            dp[i][0] =Math.max(dp[i-1][0],Math.max(dp[i - 1][3], dp[i - 1][1])-prices[i]);
            dp[i][1] =Math.max(dp[i-1][1],dp[i-1][3]);
            dp[i][2] =dp[i-1][0]+prices[i];
            dp[i][3] = dp[i-1][2];
        }

        return Math.max(dp[prices.length- 1][3],Math.max(dp[prices.length - 1][1], dp[prices.length- 1][2]));
    }
}

714. 买卖股票的最佳时机含手续费

714. 买卖股票的最佳时机含手续费

难度中等763收藏分享切换为英文接收动态反馈

给定一个整数数组 prices，其中 prices[i]表示第 i 天的股票价格 ；整数 fee 代表了交易股票的手续费用。

你可以无限次地完成交易，但是你每笔交易都需要付手续费。如果你已经购买了一个股票，在卖出它之前你就不能再继续购买股票了。

返回获得利润的最大值。

注意：这里的一笔交易指买入持有并卖出股票的整个过程，每笔交易你只需要为支付一次手续费。

示例 1：

输入：prices = [1, 3, 2, 8, 4, 9], fee = 2
输出：8
解释：能够达到的最大利润:  
在此处买入 prices[0] = 1
在此处卖出 prices[3] = 8
在此处买入 prices[4] = 4
在此处卖出 prices[5] = 9
总利润: ((8 - 1) - 2) + ((9 - 4) - 2) = 8

示例 2：

输入：prices = [1,3,7,5,10,3], fee = 3
输出：6 

提示：

• 1 <= prices.length <= 5 * 104
• 1 <= prices[i] < 5 * 104
• 0 <= fee < 5 * 104

解答

class Solution {
    public int maxProfit(int[] prices, int fee) {
        // dp[i][0] 表示第i天持有股票所省最多现金。 dp[i][1] 表示第i天不持有股票所得最多现金
        int [][]dp=new int[prices.length][2];
        dp[0][0]=-prices[0];
        for (int i = 1; i < prices.length; 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-1][0]+prices[i]-fee);
        }

        return Math.max(dp[prices.length - 1][0], dp[prices.length - 1][1]);

    }
}

674 最长连续递增子序列

674. 最长连续递增序列

难度简单317收藏分享切换为英文接收动态反馈

给定一个未经排序的整数数组，找到最长且 连续递增的子序列，并返回该序列的长度。

连续递增的子序列 可以由两个下标 l 和 r（l < r）确定，如果对于每个 l <= i < r，都有 nums[i] < nums[i + 1] ，那么子序列 [nums[l], nums[l + 1], ..., nums[r - 1], nums[r]] 就是连续递增子序列。

示例 1：

输入：nums = [1,3,5,4,7]
输出：3
解释：最长连续递增序列是 [1,3,5], 长度为3。
尽管 [1,3,5,7] 也是升序的子序列, 但它不是连续的，因为 5 和 7 在原数组里被 4 隔开。 

示例 2：

输入：nums = [2,2,2,2,2]
输出：1
解释：最长连续递增序列是 [2], 长度为1。

解答

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

    }
}

718 最长重复子数组

718. 最长重复子数组](https://leetcode.cn/problems/maximum-length-of-repeated-subarray/)

难度中等768收藏分享切换为英文接收动态反馈

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

示例 1：

输入：nums1 = [1,2,3,2,1], nums2 = [3,2,1,4,7]
输出：3
解释：长度最长的公共子数组是 [3,2,1] 。

示例 2：

输入：nums1 = [0,0,0,0,0], nums2 = [0,0,0,0,0]
输出：5

提示：

• 1 <= nums1.length, nums2.length <= 1000
• 0 <= nums1[i], nums2[i] <= 100

解答

class Solution {
    public int findLength(int[] nums1, int[] nums2) {
       //dp[i][j]定义为以下标为i-1 和j-1组成的子数组  最长重复的值
        //这里数组定义为nums.length+1  是方便我们不同初始化0值
        int [][]dp=new int[nums1.length+1][nums2.length+1];
        int res=0;
        for (int i = 1; i <nums1.length+1 ; i++) {
            for (int j = 1; j <nums2.length+1; 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;

    }
}

解答2

class Solution {
    public int findLength(int[] nums1, int[] nums2) {
      //dp[i][j]定义为以下标为i 和j组成的子数组  最长重复的值
        int [][]dp=new int[nums1.length][nums2.length];

        int res=0;
        for (int i = 0; i <nums2.length ; i++) {
            if(nums1[0]==nums2[i]){
                dp[0][i]=1;
                res=1;
            }
        }

        for (int i = 0; i <nums1.length ; i++) {
            if(nums2[0]==nums1[i]){
                dp[i][0]=1;
                res=1;
            }
        }

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

    }
}

1143 最长公共子序列

1143. 最长公共子序列

难度中等1076收藏分享切换为英文接收动态反馈

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

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

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

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

示例 1：

输入：text1 = "abcde", text2 = "ace" 
输出：3  
解释：最长公共子序列是 "ace" ，它的长度为 3 。

示例 2：

输入：text1 = "abc", text2 = "abc"
输出：3
解释：最长公共子序列是 "abc" ，它的长度为 3 。

示例 3：

输入：text1 = "abc", text2 = "def"
输出：0
解释：两个字符串没有公共子序列，返回 0 

解答

/**
对于公共子序列问题  这样定义会更简单
因为这样定义  初始化 索引0时更加方便
**/
class Solution {
    public int longestCommonSubsequence(String text1, String text2) {
        //dp[i][j]：长度为[0, i - 1]的字符串text1与长度为[0, j - 1]的字符串text2的最长公共子序列为dp[i][j]
          int [][]dp=new int[text1.length()+1][text2.length()+1];
        for (int i = 1; i < text1.length()+1; i++) {
            char c=text1.charAt(i-1);
            for (int j = 1; j < text2.length()+1; j++) {
                char c2=text2.charAt(j-1);
                if(c==c2){
                    dp[i][j]=dp[i-1][j-1]+1;
                }else{
                    dp[i][j]=Math.max(dp[i-1][j],dp[i][j-1]);
                }
            }
        }
        return  dp[text1.length()][text2.length()];

    }
}

解答2

//这样定义的话  会比较 
public static int longestCommonSubsequence(String text1, String text2) {
        int [][]dp=new int[text1.length()][text2.length()];
        char c1 = text1.charAt(0);
        char c2 = text2.charAt(0);
        int res=0;
        for (int i = 0; i < text2.length(); i++) {
            if(c1==text2.charAt(i)){
                dp[0][i]=1;
                res=1;
            }
            dp[0][i]=res;
        }
        res=0;
        for (int i = 0; i < text1.length(); i++) {
            if(c2==text1.charAt(i)){
                dp[i][0]=1;
                res=1;
            }
            dp[i][0]=res;
        }
        for (int i = 1; i <text1.length() ; i++) {
            for (int j = 1; j <text2.length() ; j++) {
                if(text1.charAt(i)==text2.charAt(j)){
                    dp[i][j]=dp[i-1][j-1]+1;
                }else{
                    dp[i][j]=Math.max(dp[i-1][j],dp[i][j-1]);
                }

            }
        }

        return dp[text1.length()-1][text2.length()-1];

    }

1035 不相交的线

1035. 不相交的线

在两条独立的水平线上按给定的顺序写下 nums1 和 nums2 中的整数。

现在，可以绘制一些连接两个数字 nums1[i] 和 nums2[j] 的直线，这些直线需要同时满足满足：

• nums1[i] == nums2[j]
• 且绘制的直线不与任何其他连线（非水平线）相交。

请注意，连线即使在端点也不能相交：每个数字只能属于一条连线。

以这种方法绘制线条，并返回可以绘制的最大连线数。

示例 1：

输入：nums1 = [1,4,2], nums2 = [1,2,4]
输出：2
解释：可以画出两条不交叉的线，如上图所示。 
但无法画出第三条不相交的直线，因为从 nums1[1]=4 到 nums2[2]=4 的直线将与从 nums1[2]=2 到 nums2[1]=2 的直线相交。

示例 2：

输入：nums1 = [2,5,1,2,5], nums2 = [10,5,2,1,5,2]
输出：3

示例 3：

输入：nums1 = [1,3,7,1,7,5], nums2 = [1,9,2,5,1]
输出：2

解答

public  int maxUncrossedLines(int[] nums1, int[] nums2) {
    int [][]dp=new int[nums1.length+1][nums2.length+1];
    for (int i = 1; i <nums1.length+1 ; i++) {
        int x1=nums1[i-1];
        for (int j = 1; j < nums2.length+1; j++) {
            int x2=nums2[j-1];
            if (x1==x2){
                dp[i][j]=dp[i-1][j-1]+1;
            }else {
                dp[i][j]=Math.max(dp[i-1][j],dp[i][j-1]);
            }
        }
    }
    return dp[nums1.length][nums2.length];

}

53 最大子数组和

53. 最大子数组和

难度中等5191收藏分享切换为英文接收动态反馈

给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

子数组 是数组中的一个连续部分。

示例 1：

输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
输出：6
解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。

示例 2：

输入：nums = [1]
输出：1

示例 3：

输入：nums = [5,4,-1,7,8]
输出：23

解答

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

392 判断子序列

392. 判断子序列

难度简单708收藏分享切换为英文接收动态反馈

给定字符串 s 和 t ，判断 s 是否为 t 的子序列。

字符串的一个子序列是原始字符串删除一些（也可以不删除）字符而不改变剩余字符相对位置形成的新字符串。（例如，"ace"是"abcde"的一个子序列，而"aec"不是）。

进阶：

如果有大量输入的 S，称作 S1, S2, … , Sk 其中 k >= 10亿，你需要依次检查它们是否为 T 的子序列。在这种情况下，你会怎样改变代码？

致谢：

特别感谢 @pbrother 添加此问题并且创建所有测试用例。

示例 1：

输入：s = "abc", t = "ahbgdc"
输出：true

示例 2：

输入：s = "axc", t = "ahbgdc"
输出：false

提示：

• 0 <= s.length <= 100
• 0 <= t.length <= 10^4
• 两个字符串都只由小写字符组成。

解答

class Solution {
    public boolean isSubsequence(String s, String t) {
        int length1 = s.length(); int length2 = t.length();
        int[][] dp = new int[length1+1][length2+1];
        for(int i = 1; i <= length1; i++){
            for(int j = 1; j <= length2; j++){
                if(s.charAt(i-1) == t.charAt(j-1)){
                    dp[i][j] = dp[i-1][j-1] + 1;
                }else{
                    dp[i][j] = dp[i][j-1];
                }
            }
        }
        if(dp[length1][length2] == length1){
            return true;
        }else{
            return false;
        }

    }
}

647 回文子串

647. 回文子串

难度中等942

给你一个字符串 s ，请你统计并返回这个字符串中 回文子串 的数目。

回文字符串 是正着读和倒过来读一样的字符串。

子字符串 是字符串中的由连续字符组成的一个序列。

具有不同开始位置或结束位置的子串，即使是由相同的字符组成，也会被视作不同的子串。

示例 1：

输入：s = "abc"
输出：3
解释：三个回文子串: "a", "b", "c"

示例 2：

输入：s = "aaa"
输出：6
解释：6个回文子串: "a", "a", "a", "aa", "aa", "aaa"

解答

class Solution {
    public int countSubstrings(String s) {
         if(s.length()==1){
             return 1;
         }
         boolean [][]dp=new boolean[s.length()][s.length()];
        for (int i = 0; i <s.length() ; i++) {
            for (int j = 0; j <=i ; j++) {
                if(s.charAt(i)==s.charAt(j)){
                    if(i-j<3){
                        dp[i][j]=true;
                    }else{
                        dp[i][j]=dp[i-1][j+1];
                    }
                }else{
                    dp[i][j]=false;
                }

            }
        }
        int ans=0;

        for (int i = 0; i < s.length(); i++) {
            for (int j = 0; j < s.length(); j++) {
                if (dp[i][j]) ans++;
            }
        }
        return ans;


    }
}

516 最长回文子串

516. 最长回文子序列

难度中等859

给你一个字符串 s ，找出其中最长的回文子序列，并返回该序列的长度。

子序列定义为：不改变剩余字符顺序的情况下，删除某些字符或者不删除任何字符形成的一个序列。

示例 1：

输入：s = "bbbab"
输出：4
解释：一个可能的最长回文子序列为 "bbbb" 。

示例 2：

输入：s = "cbbd"
输出：2
解释：一个可能的最长回文子序列为 "bb" 。

解答

class Solution {
    public int longestPalindromeSubseq(String s) {
        
        //dp[i][j]：字符串s在[i, j]范围内最长的回文子序列的长度为dp[i][j]。
        int [][]dp=new int[s.length()][s.length()];
        for (int i = s.length()-1; i >=0 ; i--) {
            dp[i][i]=1;
            for (int j = i+1; j <s.length() ; j++) {
                if(s.charAt(j)==s.charAt(i)){
                    dp[i][j]=dp[i+1][j-1]+2;
                }else{
                    dp[i][j]=Math.max(dp[i][j-1],dp[i+1][j]);
                }

            }
        }
        return dp[0][s.length()-1];

    }
}