发表更新2 小时读完 (大约15085个字)

leetcode-动态规划

动态规划

1、斐波那契数 509

https://leetcode.cn/problems/fibonacci-number/description/

斐波那契数 （通常用 F(n) 表示）形成的序列称为 斐波那契数列 。该数列由 0 和 1 开始，后面的每一项数字都是前面两项数字的和。也就是：

1
2
F(0) = 0，F(1) = 1
F(n) = F(n - 1) + F(n - 2)，其中 n > 1

给定 n ，请计算 F(n) 。

示例 1：

1
2
3
输入：n = 2
输出：1
解释：F(2) = F(1) + F(0) = 1 + 0 = 1

示例 2：

1
2
3
输入：n = 3
输出：2
解释：F(3) = F(2) + F(1) = 1 + 1 = 2

示例 3：

1
2
3
输入：n = 4
输出：3
解释：F(4) = F(3) + F(2) = 2 + 1 = 3

提示：

  • 0 <= n <= 30
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    public int fib(int n) {
        if (n < 2) return n;
        int[] dp = new int[2];
        dp[0] = 0;
        dp[1] = 1;
        int sum = 0;
        for (int i = 2; i <= n; i++) {
            sum = dp[0] + dp[1];
            dp[0] = dp[1];
            dp[1] = sum;
        }
        return sum;
    }
}

2、爬楼梯 70

https://leetcode.cn/problems/climbing-stairs/description/

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。

每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

示例 1：

1
2
3
4
5
输入：n = 2
输出：2
解释：有两种方法可以爬到楼顶。
1. 1 阶 + 1 阶
2. 2 阶

示例 2：

1
2
3
4
5
6
输入：n = 3
输出：3
解释：有三种方法可以爬到楼顶。
1. 1 阶 + 1 阶 + 1 阶
2. 1 阶 + 2 阶
3. 2 阶 + 1 阶

提示：

  • 1 <= n <= 45
1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    public int climbStairs(int n) {
        if (n < 2) return n;
        int low = 1;
        int high = 1;
        int sum = 0;
        for (int i = 2; i <= n; i++) {
            sum = low + high;
            low = high;
            high = sum;
        }
        return sum;
    }
}

3、使用最小花费爬楼梯

https://leetcode.cn/problems/min-cost-climbing-stairs/

给你一个整数数组 cost ，其中 cost[i] 是从楼梯第 i 个台阶向上爬需要支付的费用。一旦你支付此费用，即可选择向上爬一个或者两个台阶。

你可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯。

请你计算并返回达到楼梯顶部的最低花费。

示例 1：

1
2
3
4
5
输入：cost = [10,15,20]
输出：15
解释：你将从下标为 1 的台阶开始。
- 支付 15 ，向上爬两个台阶，到达楼梯顶部。
总花费为 15 。

示例 2：

1
2
3
4
5
6
7
8
9
10
输入：cost = [1,100,1,1,1,100,1,1,100,1]
输出：6
解释：你将从下标为 0 的台阶开始。
- 支付 1 ，向上爬两个台阶，到达下标为 2 的台阶。
- 支付 1 ，向上爬两个台阶，到达下标为 4 的台阶。
- 支付 1 ，向上爬两个台阶，到达下标为 6 的台阶。
- 支付 1 ，向上爬一个台阶，到达下标为 7 的台阶。
- 支付 1 ，向上爬两个台阶，到达下标为 9 的台阶。
- 支付 1 ，向上爬一个台阶，到达楼梯顶部。
总花费为 6 。

提示：

  • 2 <= cost.length <= 1000
  • 0 <= cost[i] <= 999
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public int minCostClimbingStairs(int[] cost) {
      if (cost.length < 2) {
        return 0;
      }
      int dp0 = 0;
      int dp1 = 0;
      int sum = 0;
      for (int i = 2; i <= cost.length; i++) {
        sum = Math.min(dp0+cost[i-2], dp1+cost[i-1]);
        dp0 = dp1;
        dp1 = sum;
      }  
      return sum;
    }
}

4、不同路径

https://leetcode.cn/problems/unique-paths/description/

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

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

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

示例 1：

img

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

示例 2：

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

示例 3：

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

示例 4：

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

提示：

  • 1 <= m, n <= 100
  • 题目数据保证答案小于等于 2 * 109
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public int uniquePaths(int m, int n) {
        int [][]dp = new int[m][n];
        for (int i = 0; i < m; i++) {
            dp[i][0] = 1;
        }; 
        for (int j = 0; j < n; j++) {
            dp[0][j] = 1;
        }
        for (int i = 1; i < m; i++) {
            for (int j = 1; i < n; j++) {
                dp[i][j] = dp[i-1][j] + dp[i][j-1];
            }
        }        
        return dp[m-1][n-1];
    }
}

5、不同路径II

https://leetcode.cn/problems/unique-paths-ii/

给定一个 m x n 的整数数组 grid。一个机器人初始位于 左上角（即 grid[0][0]）。机器人尝试移动到 右下角（即 grid[m - 1][n - 1]）。机器人每次只能向下或者向右移动一步。

网格中的障碍物和空位置分别用 1 和 0 来表示。机器人的移动路径中不能包含 任何 有障碍物的方格。

返回机器人能够到达右下角的不同路径数量。

测试用例保证答案小于等于 2 * 109。

示例 1：

img

1
2
3
4
5
6
输入：obstacleGrid = [[0,0,0],[0,1,0],[0,0,0]]
输出：2
解释：3x3 网格的正中间有一个障碍物。
从左上角到右下角一共有 2 条不同的路径：
1. 向右 -> 向右 -> 向下 -> 向下
2. 向下 -> 向下 -> 向右 -> 向右

示例 2：

img

1
2
输入：obstacleGrid = [[0,1],[0,0]]
输出：1

提示：

  • m == obstacleGrid.length
  • n == obstacleGrid[i].length
  • 1 <= m, n <= 100
  • obstacleGrid[i][j] 为 0 或 1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
class Solution {
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        int m = obstacleGrid.length;
        int n = obstacleGrid[0].length;
        int [][]dp = new int[m][n];
        int label = 1;
        int label2 = 1;
        for (int i = 0; i < m; i++) {
            if (obstacleGrid[i][0] == 1) {
                label = 0;
            }
            dp[i][0] = label;
        }
        for (int j = 0; j < n; j++) {
            if (obstacleGrid[0][j] == 1) {
                label2 = 0;
            }
            dp[0][j] = label2;
        }
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                if (obstacleGrid[i][j-1] == 0 && obstacleGrid[i-1][j] == 0) {
                    dp[i][j] = dp[i][j-1] + dp[i-1][j];
                }else if (obstacleGrid[i][j-1] == 1 && obstacleGrid[i-1][j] == 1) {
                    dp[i][j] = 0;
                }else if (obstacleGrid[i][j-1] == 1) {
                    dp[i][j] = dp[i-1][j];
                }else if (obstacleGrid[i-1][j] == 1) {
                    dp[i][j] = dp[i][j-1];
                }
            }
        }
        if (obstacleGrid[m-1][n-1] == 1) {
            return 0;
        } else {
            return dp[m-1][n-1]; 
        }                   
    }
}

6、整数拆分

https://leetcode.cn/problems/integer-break/description/

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

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

示例 1:

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

示例 2:

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

提示:

  • 2 <= n <= 58
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    public int integerBreak(int n) {
        // dpn 表示n这个整数拆分后的最大乘积值
        int[]dp = new int[n+1];
        dp[0] = 0;
        dp[0] = 0;
        dp[2] = 1;
        for (int i = 3; i <= n; i++){
            for (int j = 1; j < i; j++) {
                dp[i] = Math.max(dp[i],Math.max(j*(i-j), j*dp[i-j]));
            }
        }
        return dp[n];
     }
}

7、不同的二叉搜索树

https://leetcode.cn/problems/unique-binary-search-trees/description/

给你一个整数 n ，求恰由 n 个节点组成且节点值从 1 到 n 互不相同的 二叉搜索树 有多少种？返回满足题意的二叉搜索树的种数。

示例 1：

img

1
2
输入：n = 3
输出：5

示例 2：

1
2
输入：n = 1
输出：1

提示：

  • 1 <= n <= 19
1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
    public int numTrees(int n) {
        int dp [] = new int[n+1];
        dp[0] = 1;
        dp[1] = 1; 
        for (int i = 2; i <= n; i++) {
            for (int j = 0 ; j < i; j++) {
                dp[i] += dp[j]*dp[i-j-1];
            }
        }
        return dp[n];
    }
}

8、01背包问题

题目描述

小明是一位科学家，他需要参加一场重要的国际科学大会，以展示自己的最新研究成果。他需要带一些研究材料，但是他的行李箱空间有限。这些研究材料包括实验设备、文献资料和实验样本等等，它们各自占据不同的空间，并且具有不同的价值。

小明的行李空间为 N，问小明应该如何抉择，才能携带最大价值的研究材料，每种研究材料只能选择一次，并且只有选与不选两种选择，不能进行切割。

输入描述

第一行包含两个正整数，第一个整数 M 代表研究材料的种类，第二个正整数 N，代表小明的行李空间。

第二行包含 M 个正整数，代表每种研究材料的所占空间。

第三行包含 M 个正整数，代表每种研究材料的价值。

输出描述

输出一个整数，代表小明能够携带的研究材料的最大价值。

输入示例
1
2
3
6 1
2 2 3 1 5 2
2 3 1 5 4 3
输出示例
1
5
提示信息

小明能够携带 6 种研究材料，但是行李空间只有 1，而占用空间为 1 的研究材料价值为 5，所以最终答案输出 5。

数据范围：
1 <= N <= 5000
1 <= M <= 5000
研究材料占用空间和价值都小于等于 1000

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
import java.util.*;

public class Main{
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int M = scanner.nextInt();
        int N = scanner.nextInt();
        
        int[] weight = new int[M];
        int[] value = new int[M];
        
        for (int i = 0; i < M; i++) {
            weight[i] = scanner.nextInt();
        }
        for (int i = 0; i < M; i++) {
            value[i] = scanner.nextInt();
        }
        int dp[] = new int[N + 1];
        for (int i = 0; i < M ; i++) {
            for (int j = N; j >= weight[i];j--) {
                dp[j] = Math.max(dp[j],dp[j - weight[i]]+value[i]);
            }
        }
        System.out.println(dp[N]);
    }
    
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int M = scanner.nextInt();  // 物品数量
        int N = scanner.nextInt();  // 背包容量
        
        int[] weight = new int[M];  // 物品重量
        int[] value = new int[M];   // 物品价值
        
        for (int i = 0; i < M; i++) {
            weight[i] = scanner.nextInt();
        }
        for (int i = 0; i < M; i++) {
            value[i] = scanner.nextInt();
        }
        
        // 初始化二维DP数组，行数是M+1，列数是N+1
        int[][] dp = new int[M + 1][N + 1];
        
        // 动态规划计算最大价值
        for (int i = 1; i <= M; i++) {
            for (int j = 0; j <= N; j++) {
                if (j >= weight[i - 1]) {  // 如果当前背包容量大于等于物品i的重量
                    // 选择放入当前物品与不放入当前物品的最大价值
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - weight[i - 1]] + value[i - 1]);
                } else {
                    // 当前背包容量不足以放入物品i，保持不变
                    dp[i][j] = dp[i - 1][j];
                }
            }
        }
        
        // 输出最大价值
        System.out.println(dp[M][N]);
    }
}

9、分割等和子集

https://leetcode.cn/problems/partition-equal-subset-sum/description/

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

示例 1：

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

示例 2：

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

提示：

  • 1 <= nums.length <= 200
  • 1 <= nums[i] <= 100
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
import java.util.Arrays;
import java.util.stream.IntStream;

class Solution {
    public boolean canPartition(int[] nums) {
        // 01背包问题，背包容量为数组和的一半，物体的重量和价值为数值
        // int sum = Arrays.stream(nums).sum();   
        int sum = IntStream.of(nums).sum();
        int half = sum / 2;
        if (sum % 2 == 1) {
            return false;
        }
        int []dp = new int[half+1];
        for (int i = 0; i < nums.length; i++) {
            for (int j = half; j >= nums[i]; j--) {
                dp[j] = Math.max(dp[j],dp[j-nums[i]]+nums[i]);
            }
        }
        if (dp[half] == half) {
            return true;
        } else return false;
    }
}

10、最后一块石头的重量II

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

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

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

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

示例 1：

1
2
3
4
5
6
7
输入：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：

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

提示：

  • 1 <= stones.length <= 30
  • 1 <= stones[i] <= 100
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
import java.util.stream.IntStream;

class Solution {
    public int lastStoneWeightII(int[] stones) {
        // 转化为01背包问题，看容量为总和的一半的背包最多可以装多上价值的石头
        int sum = IntStream.of(stones).sum();
        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];

    }
}

11、目标和

https://leetcode.cn/problems/target-sum/

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

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

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

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

示例 1：

1
2
3
4
5
6
7
8
输入：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：

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

提示：

  • 1 <= nums.length <= 20
  • 0 <= nums[i] <= 1000
  • 0 <= sum(nums[i]) <= 1000
  • -1000 <= target <= 1000
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
import java.util.stream.IntStream;

class Solution {
    public int findTargetSumWays(int[] nums, int target) {
        /* 
         * left 表示正数，right 表示负数，left + right = target, left - right = sum
         * left = target + sum /2，如果不是整数说明不存在这样的构造方法
         * dp[j] 表示装满j容量的背包，总共有多少种不同的方法
         * 先考虑二维数组的情况，dp[i][j] = dp[i-1][j] + dp[i-1][j-nums[i]];
         * 表示为不用最后一个数字填满容量，和使用最后一个数字填满容量 这两种情况
         * dp[j] =  dp[j] + dp [j-nums[i]];
         */
        int sum = IntStream.of(nums).sum();
        int left = target + sum;
        if (left % 2 == 1 || left < 0) {
            return 0;
        } else {
            left = left / 2;
        }
        int [] dp = new int [left + 1];
        dp[0] = 1;
        for (int i = 0; i < nums.length; i++) {
            for (int j = left; j >= nums[i]; j--) {
                dp[j] = dp[j] + dp[j - nums[i]]; 
            }
        }
        return dp[left];
    }
}

12、一和零

https://leetcode.cn/problems/ones-and-zeroes/description/

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

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

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

示例 1：

1
2
3
4
输入：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：

1
2
3
输入：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
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
    public int findMaxForm(String[] strs, int m, int n) {
        int[][][] dp = new int[strs.length+1][m+1][n+1];
        for (int i = 1; i <= strs.length; i++) {
            int zeros = 0, ones = 0;
            for (char ch : strs[i-1].toCharArray()) {
                if (ch == '1') {
                    ones++;
                } else {
                    zeros++;
                }
            }
            for (int j = 0; j <= m; j++) {
                for (int k = 0; k <= n; k++) {
                    if (j >= zeros && k >= ones) {
                        dp[i][j][k] = Math.max(dp[i-1][j][k],dp[i-1][j-zeros][k-ones] + 1); 
                    }else {
                        dp[i][j][k] = dp[i-1][j][k];
                    } 
                }
            }
        }
        return dp[strs.length][m][n];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
    public int findMaxForm(String[] strs, int m, int n) {
        int [][] dp = new int [m+1][n+1];
        int zeros = 0 , ones = 0; 
        for (String str : strs) {
            zeros = 0; 
            ones = 0;
            for(char ch : str.toCharArray()) {
                if (ch == '1') {
                    ones ++;
                } else {
                    zeros++;
                }
            }
            for (int i = m; i >= zeros; i--) {
                for (int j = n; j >= ones; j--) {
                    dp[i][j] = Math.max(dp[i][j], dp[i-zeros][j-ones]+1);
                }
            }

        }
        return dp[m][n];
    }
}

13、01背包和完全背包

0/1 背包问题和完全背包问题虽然都是经典的背包问题，但它们在物品选择上有很大的区别。以下是两者的区别和解法差异：

  1. 物品选择限制：

  • 0/1 背包问题

    ：每个物品只能选择一次。对于每种物品，我们只能选择放入背包或不放入背包。

    • 例如：如果有 3 种物品，背包的容量为 5，你只能选择其中某些物品，且每种物品只能选择一次。

  • 完全背包问题

    ：每个物品可以选择无数次。对于每种物品，我们可以选择放入背包任意多次，只要背包容量允许。

    • 例如：如果有 3 种物品，背包的容量为 5，你可以选择同一种物品放入背包多次，直到背包装满。
  1. 动态规划的转移方程差异：
  • 0/1 背包问题的状态转移方程：
    • 对于每个物品 i 和每个背包容量 j，如果我们决定 **不选物品 i**，那么 dp[i][j] = dp[i-1][j]（即不选择物品 i 时，价值就是选择前 i-1 种物品时的最大值）。
    • 如果我们决定 **选物品 i**，那么 dp[i][j] = dp[i-1][j-w[i]] + v[i]（即选择物品 i 时，价值就是选择前 i-1 种物品时，剩余容量的最大值 + 物品 i 的价值）。
  • 完全背包问题的状态转移方程：
    • 对于每个物品 i 和每个背包容量 j，如果我们决定 **不选物品 i**，则 dp[i][j] = dp[i-1][j]（即不选择物品 i 时，价值就是选择前 i-1 种物品时的最大值）。
    • 如果我们决定 **选物品 i**，那么 dp[i][j] = dp[i][j - w[i]] + v[i]（注意，物品可以重复选择，因此这里 i 仍然不变，而是对背包容量逐渐递减）。这意味着如果 j 足够大，我们可以重复选择物品 i，直到容量用尽。
  1. 动态规划数组的使用差异：
  • 0/1 背包问题：通常用二维数组 dp[i][j] 表示前 i 个物品，背包容量为 j 时的最大价值。每次物品只能选择一次，所以在更新 dp[i][j] 时，我们只能参考 dp[i-1][j] 和 dp[i-1][j-w[i]] + v[i]。
  • 完全背包问题：可以使用一维数组 dp[j]，表示背包容量为 j 时的最大价值。由于每个物品可以选择多次，因此我们需要从当前容量 j 逐步递减更新。在每次选择物品时，当前物品可能被选多次，所以状态转移时可能会使用 dp[j - w[i]] + v[i] 来更新当前容量。
  1. 示例解析：

0/1 背包问题：

输入：

1
2
3
4
5
复制代码4 5
1 2
2 4
3 4
4 5
  • 物品有 4 种，背包容量为 5。
  • 每种物品只能选择一次。

物品的重量和价值分别为：

1
2
3
4
scss复制代码(1, 2)
(2, 4)
(3, 4)
(4, 5)

解法：

  • 我们会使用动态规划数组 dp[i][j]，表示在选择前 i 种物品时，背包容量为 j 时的最大价值。
  • 对于每个物品，如果背包容量足够，我们可以选择放入背包，或者跳过该物品。

状态转移方程：

  • 对于每种物品，我们有两种选择：不选择该物品，或者选择该物品（如果容量足够）。

完全背包问题：

输入：

1
2
3
4
5
复制代码4 5
1 2
2 4
3 4
4 5
  • 物品有 4 种，背包容量为 5。
  • 每种物品可以选择多次。

物品的重量和价值分别为：

1
2
3
4
scss复制代码(1, 2)
(2, 4)
(3, 4)
(4, 5)

解法：

  • 我们使用动态规划数组 dp[j]，表示背包容量为 j 时的最大价值。
  • 对于每个物品，我们从容量 j 递减更新 dp[j]。对于容量 j，我们可以选择放入该物品，并且该物品可能被放入多次。

状态转移方程：

  • 对于每种物品 i，我们可以选择放入背包，直到背包无法再装下该物品。
  1. 代码实现差异：

0/1 背包问题：

1
2
3
4
5
6
java复制代码
for (int i = 1; i <= n; i++) {
    for (int j = v; j >= w[i-1]; j--) {
        dp[j] = Math.max(dp[j], dp[j - w[i-1]] + v[i-1]);
    }
}
  • 在 0/1 背包问题中，内层循环 j 从背包容量 v 到 w[i-1] 递减，这样可以保证每个物品只能选一次。

完全背包问题：

1
2
3
4
5
6
java复制代码
for (int i = 1; i <= n; i++) {
    for (int j = w[i-1]; j <= v; j++) {
        dp[j] = Math.max(dp[j], dp[j - w[i-1]] + v[i-1]);
    }
}
  • 在完全背包问题中，内层循环 j 从物品的重量 w[i-1] 开始递增，这样允许物品选择多次。

总结：

  • 0/1 背包问题：每种物品只能选择一次，因此在动态规划更新时，必须保证每个物品最多使用一次，通常通过从背包容量的高到低更新 dp 数组来实现。
  • 完全背包问题：每种物品可以选择多次，因此在动态规划更新时，不需要限制每个物品的使用次数，通常通过从背包容量的低到高更新 dp 数组来实现。

\52. 携带研究材料（第七期模拟笔试）

题目描述

小明是一位科学家，他需要参加一场重要的国际科学大会，以展示自己的最新研究成果。他需要带一些研究材料，但是他的行李箱空间有限。这些研究材料包括实验设备、文献资料和实验样本等等，它们各自占据不同的重量，并且具有不同的价值。

小明的行李箱所能承担的总重量是有限的，问小明应该如何抉择，才能携带最大价值的研究材料，每种研究材料可以选择无数次，并且可以重复选择。

输入描述

第一行包含两个整数，n，v，分别表示研究材料的种类和行李所能承担的总重量

接下来包含 n 行，每行两个整数 wi 和 vi，代表第 i 种研究材料的重量和价值

输出描述

输出一个整数，表示最大价值。

输入示例
1
2
3
4
5
4 5
1 2
2 4
3 4
4 5
输出示例
1
10
提示信息

第一种材料选择五次，可以达到最大值。

数据范围：

1 <= n <= 10000;
1 <= v <= 10000;
1 <= wi, vi <= 10^9.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
import java.util.Scanner;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int v = sc.nextInt();
        int [][] dp = new int[n+1][v+1];
        int [] w = new int[n];
        int [] val = new int [n];
        for (int i = 0 ; i < n; i++) {
            w[i] = sc.nextInt();
            val[i] = sc.nextInt();
        }
        for (int i = 1; i <= n; i++){
            for (int j = 0; j <= v; j++) {
                dp[i][j] = dp[i-1][j];
                if (j >= w[i-1]) {
                    dp[i][j] = Math.max(dp[i-1][j],dp[i][j-w[i-1]]+val[i-1]);
                }
            }
        }
        System.out.println(dp[n][v]);
        
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        
        // 输入n和v
        int n = sc.nextInt();
        int v = sc.nextInt();
        
        // dp数组，表示背包容量j时能获得的最大价值
        int[] dp = new int[v + 1];
        
        // 输入每种物品的重量和价值
        for (int i = 0; i < n; i++) {
            int wi = sc.nextInt();
            int vi = sc.nextInt();
            
            // 完全背包问题的核心逻辑
            // 注意这里是从当前容量v到wi倒序遍历
            for (int j = wi; j <= v; j++) {
                dp[j] = Math.max(dp[j], dp[j - wi] + vi);
            }
        }
        
        // 输出最大价值
        System.out.println(dp[v]);
    }
}

14、零钱兑换II

https://leetcode.cn/problems/coin-change-ii/description/

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

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

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

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

示例 1：

1
2
3
4
5
6
7
输入：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：

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

示例 3：

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

提示：

  • 1 <= coins.length <= 300
  • 1 <= coins[i] <= 5000
  • coins 中的所有值 互不相同
  • 0 <= amount <= 5000
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    public int change(int amount, int[] coins) {
        // dp[j]表示凑成amout金额的方案的数量
        // 用前i-1种钱币凑成总额，不使用最后一种钱币，或者使用最后一种钱币，即前i-1种钱币凑成amout-coins[i]总额的钱币
        // 方案数表示为  dp[i][j] = dp[i-1][j] + dp[i-1][j-coins[i]]
        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];
    }
}

15、组合总和IV

https://leetcode.cn/problems/combination-sum-iv/description/

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

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

示例 1：

1
2
3
4
5
6
7
8
9
10
11
12
输入：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：

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

提示：

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

进阶：如果给定的数组中含有负数会发生什么？问题会产生何种变化？如果允许负数出现，需要向题目中添加哪些限制条件？

1
2
3
4
5
6
7
8
9
10
11
12
13
14
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];
    }
}

如果给定的数组中含有负数，则会导致出现无限长度的排列。

例如，假设数组 nums 中含有正整数 a 和负整数 −b（其中 a>0,b>0,−b<0），则有 a×b+(−b)×a=0，对于任意一个元素之和等于 target 的排列，在该排列的后面添加 b 个 a 和 a 个 −b 之后，得到的新排列的元素之和仍然等于 target，而且还可以在新排列的后面继续 b 个 a 和 a 个 −b。因此只要存在元素之和等于 target 的排列，就能构造出无限长度的排列。

如果允许负数出现，则必须限制排列的最大长度，避免出现无限长度的排列，才能计算排列数。

16、爬楼梯（进阶版）

原本是普通动态规划，进阶后为完全背包问题

https://kamacoder.com/problempage.php?pid=1067

题目描述

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。

每次你可以爬至多m (1 <= m < n)个台阶。你有多少种不同的方法可以爬到楼顶呢？

注意：给定 n 是一个正整数。

输入描述

输入共一行，包含两个正整数，分别表示n, m

输出描述

输出一个整数，表示爬到楼顶的方法数。

输入示例
1
3 2
输出示例
1
3
提示信息

数据范围：
1 <= m < n <= 32;

当 m = 2，n = 3 时，n = 3 这表示一共有三个台阶，m = 2 代表你每次可以爬一个台阶或者两个台阶。

此时你有三种方法可以爬到楼顶。

  1. 1 阶 + 1 阶 + 1 阶段
  2. 1 阶 + 2 阶
  3. 2 阶 + 1 阶
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
import java.util.*;

public class Main {
    public static void main (String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        int []dp = new int [n+1];
        dp[0] = 1;
        for (int i = 1; i <= n; i++) {
            for (int j = 1;j <= m; j++) {
                if (i >= j) {
                    dp[i] = dp[i] + dp[i-j];
                }
            }
        }
        System.out.println(dp[n]);
    }
}

17、零钱兑换

https://leetcode.cn/problems/coin-change/description/

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

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

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

示例 1：

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

示例 2：

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

示例 3：

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

提示：

  • 1 <= coins.length <= 12
  • 1 <= coins[i] <= 231 - 1
  • 0 <= amount <= 104
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
import java.util.Arrays;
class Solution {
    public int coinChange(int[] coins, int amount) {
        // dp[j] 表示凑成总金额为j的时候，所需要花费的最少硬币个数
        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);
                }                
            }
        }
        if(dp[amount] == Integer.MAX_VALUE) {
            return -1;
        }else {
            return dp[amount];
        }
    }
}

18、完全平方数

https://leetcode.cn/problems/perfect-squares/description/

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

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

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

示例 1：

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

示例 2：

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

示例 3：

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

提示：

  • 1 <= coins.length <= 12
  • 1 <= coins[i] <= 231 - 1
  • 0 <= amount <= 104
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
import java.util.Arrays;

class Solution {
    public int numSquares(int n) {
        // dp[j] 表示和为j的完全平方数的最少数量
        int[] dp = new int[n + 1];
        Arrays.fill(dp, Integer.MAX_VALUE);
        dp[0] = 0;
        for (int i = 1; i*i <= n; i++) {
            for (int j = i*i; j <= n; j++) {
                dp[j] = Math.min(dp[j], dp[j-i*i]+1);
            }
        }
        return dp[n];
    }
}

19、单词拆分

https://leetcode.cn/problems/word-break/description/

给你一个字符串 s 和一个字符串列表 wordDict 作为字典。如果可以利用字典中出现的一个或多个单词拼接出 s 则返回 true。

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

示例 1：

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

示例 2：

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

示例 3：

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

提示：

  • 1 <= s.length <= 300
  • 1 <= wordDict.length <= 1000
  • 1 <= wordDict[i].length <= 20
  • s 和 wordDict[i] 仅由小写英文字母组成
  • wordDict 中的所有字符串 互不相同
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
import java.util.HashSet;
import java.util.*;

class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        Set<String> wordSet = new HashSet<String>(wordDict);
        // dp数组表示长度为j的字符串，能不能被wordSet表示出来
        boolean[] dp = new boolean[s.length()+1];
        dp[0] = true;
        for (int i = 1; i <= s.length(); i++) {
            for (int j = 0; j < i; j++) {
                String word = s.substring(j, i);
                if (dp[j] && wordSet.contains(word)) {
                    dp[i] = true;
                }
            }
        }
        return dp[s.length()];
    }
}

20、打家劫舍

https://leetcode.cn/problems/house-robber/description/

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

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

示例 1：

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

示例 2：

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

提示：

  • 1 <= nums.length <= 100
  • 0 <= nums[i] <= 400
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
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[] 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-1], dp[i-2] + nums[i]);
        } 
        return dp[nums.length-1];
    }
}

21、打家劫舍II

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

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

示例 1：

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

示例 2：

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

示例 3：

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

提示：

  • 1 <= nums.length <= 100
  • 0 <= nums[i] <= 1000
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public int rob(int[] nums) {
        int len = nums.length-1;
        if (len == 0) {
            return nums[0];
        }
        return Math.max(robBase(nums, 1, len),robBase(nums, 0, len-1));        
    }
    public int robBase (int[] nums, int start, int end) {
        int x = 0, y = 0, z = 0;
        for (int i = start; i <= end; i++) {
            y = z;
            z = Math.max(x+nums[i], y);
            x = y;
        }
        return z;
    }
}

22 打家劫舍III

小偷又发现了一个新的可行窃的地区。这个地区只有一个入口，我们称之为 root 。

除了 root 之外，每栋房子有且只有一个“父“房子与之相连。一番侦察之后，聪明的小偷意识到“这个地方的所有房屋的排列类似于一棵二叉树”。 如果 两个直接相连的房子在同一天晚上被打劫 ，房屋将自动报警。

给定二叉树的 root 。返回 在不触动警报的情况下 ，小偷能够盗取的最高金额 。

示例 1:

img

1
2
3
输入: root = [3,2,3,null,3,null,1]
输出: 7 
解释: 小偷一晚能够盗取的最高金额 3 + 3 + 1 = 7

示例 2:

img

1
2
3
输入: root = [3,4,5,1,3,null,1]
输出: 9
解释: 小偷一晚能够盗取的最高金额 4 + 5 = 9

提示：

  • 树的节点数在 [1, 104] 范围内
  • 0 <= Node.val <= 104
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
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) {
        // 定义每个节点有两个状态dp[0]表示该节点不偷的情况下能够获得的最大金额，dp[1]表示该节点偷的情况下能够获得的最大金额
        int[] result = backTravel(root);
        return Math.max (result[0],result[1]);
    }
    public int[] backTravel (TreeNode root) {
        if (root == null) {
            return new int[]{0,0};
        }
        int[] leftResult = backTravel(root.left);
        int[] rightResult = backTravel(root.right);
        int[] result = new int[2];
        result[0] = Math.max(leftResult[0],leftResult[1]) + Math.max(rightResult[0],rightResult[1]);
        result[1] = leftResult[0] + rightResult[0] + root.val;
        return result;
    }
}

23、买卖股票的最佳时机

https://leetcode.cn/problems/best-time-to-buy-and-sell-stock/description/

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

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

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

示例 1：

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

示例 2：

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

提示：

  • 1 <= prices.length <= 105
  • 0 <= prices[i] <= 104
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public int maxProfit(int[] prices) {
        // dp[i][0]表示第i天不持有股票的最大金额，dp[i][1]表示第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], - prices[i])
        // dp[0][0] = 0;
        // dp[0][1] = -prices[i];
        int len = prices.length;
        int[][]dp = new int[len][2];
        dp[0][0] = 0;
        dp[0][1] = -prices[0];
        for (int i = 1; i < len; 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], -prices[i]);
        }
        return dp[len-1][0];        
    }
}

24、买卖股票的最佳时机II

https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-ii/submissions/

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

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

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

示例 1：

1
2
3
4
5
输入：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：

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

示例 3：

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

提示：

  • 1 <= prices.length <= 3 * 104
  • 0 <= prices[i] <= 104
1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    public int maxProfit(int[] prices) {
        int result = 0;
        if (prices.length == 1) {
            return 0;
        }
        for (int i = 1 ;i < prices.length ;i++ ) {
            if (prices[i] > prices[i-1]) {
                result += prices[i] - prices[i-1];
            }
        }
        return result;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public int maxProfit(int[] prices) {
        int len = prices.length;
        int[][] dp = new int[len][2];
        dp[0][0] = 0;
        dp[0][1] = -prices[0];
        for (int i = 1; i < len; 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]);
        }
        return dp[len-1][0];

    }
}

25、买卖股票的最佳时机III

https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-iii/description/

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

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

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

示例 1:

1
2
3
4
输入：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：

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

示例 3：

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

示例 4：

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

提示：

  • 1 <= prices.length <= 105
  • 0 <= prices[i] <= 105
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
    public int maxProfit(int[] prices) {
        /*
         * 定义五个状态，dp[i][0],表示不操作，此时持有的最大金额
         * dp[i][1]表示第一次股票持有的状态，这个状态可以延续，此时持有的最大金额
         * dp[i][2]表示第一次股票卖出的状态，这个状态可以延续，此时持有的最大金额
         * dp[i][3]表示第二次股票持有的状态，这个状态可以延续，此时持有的最大金额
         * dp[i][4]表示第二次股票卖出的状态，这个状态可以延续，此时持有的最大金额
         */
        int len = prices.length;
        int[][]dp = new int[len][5];
        dp[0][0] = 0;
        dp[0][1] = -prices[0];
        dp[0][2] = 0;
        dp[0][3] = -prices[0];
        dp[0][4] = 0;
        for (int i = 1; i < len; i++) {
            dp[i][0] = 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 Math.max(dp[len-1][2],dp[len-1][4]);
    }
}

26、买卖股票的最佳时机IV

https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-iv/description/

给你一个整数数组 prices 和一个整数 k ，其中 prices[i] 是某支给定的股票在第 i 天的价格。

设计一个算法来计算你所能获取的最大利润。你最多可以完成 k 笔交易。也就是说，你最多可以买 k 次，卖 k 次。

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

示例 1：

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

示例 2：

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

提示：

  • 1 <= k <= 100
  • 1 <= prices.length <= 1000
  • 0 <= prices[i] <= 1000
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public int maxProfit(int k, int[] prices) {
        int len = prices.length;
        int [][]dp = new int[len][2*k+1];
        //初始化
        for(int j = 1; j <2*k; j+=2) {
            if (j % 2 == 1) {
                dp[0][j] = -prices[0];
            }
        }
        //状态转移
        for (int i = 1; i < len; i++) {
            for (int j = 0; j < 2*k; 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[len-1][2*k];
    }
}

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

https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-with-cooldown/

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

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

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

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

示例 1:

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

示例 2:

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

提示：

  • 1 <= prices.length <= 5000
  • 0 <= prices[i] <= 1000
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
    public int maxProfit(int[] prices) {
        int len = prices.length;
        // 1.确定dp数组的含义
        int[][] dp = new int[len][4];
        /* 
         * 这里定义四个状态,均是该状态下持有的最大金额
         * dp[i][0] 保持持有股票的状态
         * dp[i][1] 保持卖出股票的状态 
         * dp[i][2] 卖出股票 当天
         * dp[i][3] 冷冻期 当天的后一天,不能再买
         */
        // 2.初始化dp数组
        dp[0][0] = -prices[0];
        dp[0][1] = 0;
        dp[0][2] = 0;
        dp[0][3] = 0;
        // 3.确定状态转移方程
        for (int i = 1; i < len ; 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][2]);
            dp[i][2] = dp[i-1][0] + prices[i];
            dp[i][3] = dp[i][2];
        }
        return Math.max(dp[len-1][2],dp[len-1][1]);
    }
}

28、买卖股票的最佳时机含手续费

https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-with-transaction-fee/description/

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

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

返回获得利润的最大值。

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

示例 1：

1
2
3
4
5
6
7
8
输入：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：

1
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
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public int maxProfit(int[] prices, int fee) {
        int len = prices.length;
        //1.定义dp数组
        /*
         * dp[i][0] 持有股票的状态
         * dp[i][1] 卖出股票的状态
         */
        int[][]dp = new int[len][2];
        //2.初始化dp数组
        dp[0][0] = -prices[0];
        dp[0][1] = 0;
        //3.确定状态转移方程
        for (int i = 1; i < len; 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 dp[len-1][1];
    }
}

29、最长递增子序列 300

https://leetcode.cn/problems/longest-increasing-subsequence/description/

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

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

示例 1：

1
2
3
输入：nums = [10,9,2,5,3,7,101,18]
输出：4
解释：最长递增子序列是 [2,3,7,101]，因此长度为 4 。

示例 2：

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

示例 3：

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

提示：

  • 1 <= nums.length <= 2500
  • -104 <= nums[i] <= 104

进阶：

  • 你能将算法的时间复杂度降低到 O(n log(n)) 吗?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
import java.util.Arrays;

class Solution {
    public int lengthOfLIS(int[] nums) {
        int len = nums.length;
        //1.定义dp数组
        /*
         * dp[i] 表示以nums[i]结尾的最长子序列的长度
         */
        int[] dp = new int[len];
        //2. dp数组初始化
        Arrays.fill(dp,1);
        //3. 状态转移方程
        int result = 1;
        for (int i = 1; i < len; i++) {
            for (int j = 0; j < i; j++) {
                if (nums[j] < nums[i]) {
                    dp[i] = Math.max(dp[i],dp[j]+1);
                }
            }
            result = Math.max(result, dp[i]);
        }
        return result;
    }
}

30、最长连续递增序列 674

https://leetcode.cn/problems/longest-continuous-increasing-subsequence/description/

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

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

示例 1：

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

示例 2：

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

提示：

  • 1 <= nums.length <= 104
  • -109 <= nums[i] <= 109
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
import java.util.Arrays;
class Solution {
    public int findLengthOfLCIS(int[] nums) {
        int len = nums.length;
        int[]dp = new int[len];
        Arrays.fill(dp,1);
        int result = 1;
        for (int i = 1; i < len; i++) {
            if (nums[i] > nums[i-1]) {
                dp[i] = dp[i-1] + 1;
                result = Math.max (dp[i],result);
            }
        }
        return result;
    }
}

31、最长重复子数组 718

https://leetcode.cn/problems/maximum-length-of-repeated-subarray/description/

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

示例 1：

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

示例 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
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
    public int findLength(int[] nums1, int[] nums2) {
        int len1 = nums1.length;
        int len2 = nums2.length;

        //1.定义dp数组
        /*
         * 为什么这么定义？dp[i][j]表示以nums[i-1]和nums[j-1]结尾的最长公众子数组的长度，
         * 这样在初始化的时候，第一行和第一列就是没有意义的，直接赋为0，
         * 否则的话，如果表示num[i]和nums[j]结尾的最长公共子数组的长度的话，第一行和第一列要分别进行判断，是否相等
         * 相等为1 ，不等为0
         */
        int[][]dp = new int[len1+1][len2+1];
        //2.dp数组初始化

        //3.状态转移方程
        int result = 0;
        for(int i = 1; i <= len1; i++) {
            for(int j = 1; j <= len2; j++) {
                if(nums1[i-1] == nums2[j-1]) {
                    dp[i][j] = dp[i-1][j-1] + 1;
                    result = Math.max(result,dp[i][j]);
                }
            }
        }
        return result;
    }
}

32、最长公共子序列 1143

https://leetcode.cn/problems/longest-common-subsequence/description/

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

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

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

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

示例 1：

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

示例 2：

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

示例 3：

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

提示：

  • 1 <= text1.length, text2.length <= 1000
  • text1 和 text2 仅由小写英文字符组成。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public int longestCommonSubsequence(String text1, String text2) {
        int len1 = text1.length();
        int len2 = text2.length();
        // dp[i][j] 表示以i-1和j-1结尾的字符串具有的最长公共子序列
        int[][]dp = new int[len1+1][len2+1];

        for (int i = 1; i <= len1; i++) {
            for (int j = 1; j <= len2; j++) {
                if (text1.charAt(i-1) == text2.charAt(j-1)) {
                    dp[i][j] = dp[i-1][j-1]+1;
                    System.out.println(dp[i][j]);
                }else {
                    dp[i][j] = Math.max(dp[i][j-1], dp[i-1][j]);
                }
            }
        }
        return dp[len1][len2];   
    }
}

33、不相交的线 1035

https://leetcode.cn/problems/uncrossed-lines/description/
在两条独立的水平线上按给定的顺序写下 nums1 和 nums2 中的整数。

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

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

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

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

示例 1：

img

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

示例 2：

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

示例 3：

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

提示：

  • 1 <= nums1.length, nums2.length <= 500
  • 1 <= nums1[i], nums2[j] <= 2000
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public int maxUncrossedLines(int[] nums1, int[] nums2) {
        int len1 = nums1.length;
        int len2 = nums2.length;
        int[][] dp = new int[len1+1][len2+1];
        
        for (int i = 1; i <= len1; i++) {
            for (int j = 1; j <= len2; j++) {
                if (nums1[i-1] == nums2[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[len1][len2];
    }
}

34、最大子数组和 53

https://leetcode.cn/problems/maximum-subarray/description/

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

子数组

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

示例 1：

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

示例 2：

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

示例 3：

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

提示：

  • 1 <= nums.length <= 105
  • -104 <= nums[i] <= 104

进阶：如果你已经实现复杂度为 O(n) 的解法，尝试使用更为精妙的 分治法 求解。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
// 贪心
class Solution {
    public int maxSubArray(int[] nums) {
        int result = Integer.MIN_VALUE;
        int count = 0;
        for (int i = 0; i < nums.length; i++) {
            count += nums[i];
            if(count > result) {
                result = count;
            }
            if (count < 0) {
                count = 0;
            }
        }
        return result;
        
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public int maxSubArray(int[] nums) {
        int len = nums.length;
        int[] dp = new int[len];
        dp[0] = nums[0];
        /*
         * dp[i]表示以nums[i]结尾的最大子数组和
         */
        int result = dp[0];
        for (int i = 1; i < len; i++) {
            dp[i] = Math.max(dp[i-1] + nums[i], nums[i]);
            result = Math.max(result, dp[i]); 
        }
        return result;
    }
}

35、判断子序列 392

https://programmercarl.com/0392.%E5%88%A4%E6%96%AD%E5%AD%90%E5%BA%8F%E5%88%97.html

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

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

进阶：

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

致谢：

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

示例 1：

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

示例 2：

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

提示：

  • 0 <= s.length <= 100
  • 0 <= t.length <= 10^4
  • 两个字符串都只由小写字符组成。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
    public boolean isSubsequence(String s, String t) {
        int len1 = s.length();
        int len2 = t.length();
        if (len1 > len2) {
            return false;
        }        
        int[][] dp = new int[len1+1][len2+1];
        for (int i = 1; i <= len1; i++) {
            for (int j = 1; j <= len2; j++) {
                if (s.charAt(i-1) == t.charAt(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]);
                }
            }
        }
        if (len1 == dp[len1][len2]) {
            return true;
        }else {
            return false;
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
import java.util.*;

public class SubsequenceChecker {

    // 使用二分查找和 positionMap 判断 s 是否是 t 的子序列
    public static boolean isSubsequence(String s, String t) {
        // 1. 构建 positionMap，记录每个字符在 t 中的位置
        Map<Character, List<Integer>> positionMap = new HashMap<>();
        for (int i = 0; i < t.length(); i++) {
            char c = t.charAt(i);
            positionMap.computeIfAbsent(c, k -> new ArrayList<>()).add(i);
        }

        // 2. 使用一个指针来跟踪在 t 中的位置
        int prevIndex = -1;  // 初始为 -1，表示我们还没有找到任何字符

        // 3. 遍历字符串 s
        for (char c : s.toCharArray()) {
            // 4. 如果 positionMap 中没有字符 c，直接返回 false
            if (!positionMap.containsKey(c)) {
                return false;
            }

            // 5. 获取 c 在 t 中的位置列表
            List<Integer> positions = positionMap.get(c);
            
            // 6. 用二分查找找到第一个大于 prevIndex 的位置
            int posIndex = binarySearch(positions, prevIndex);
            if (posIndex == positions.size()) {
                return false;  // 如果没有找到合适的位置，返回 false
            }
            
            // 7. 更新 prevIndex
            prevIndex = positions.get(posIndex);
        }

        return true;  // 如果遍历完 s 中所有字符都能找到对应位置，返回 true
    }

    // 二分查找：找第一个大于 prevIndex 的位置
    private static int binarySearch(List<Integer> positions, int prevIndex) {
        int left = 0, right = positions.size();
        while (left < right) {
            int mid = (left + right) / 2;
            if (positions.get(mid) > prevIndex) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        return left;
    }

    public static void main(String[] args) {
        String t = "ahbgdc";
        
        // 测试案例
        String[] queries = {"abc", "axc", "ab", "ahc"};

        for (String s : queries) {
            boolean result = isSubsequence(s, t);
            System.out.println("Is \"" + s + "\" a subsequence of \"" + t + "\"? " + result);
        }
    }
}

36、不同的子序列 115

https://leetcode.cn/problems/distinct-subsequences/description/

给你两个字符串 s 和 t ，统计并返回在 s 的 子序列 中 t 出现的个数，结果需要对 109 + 7 取模。

示例 1：

1
2
3
4
5
6
7
输入：s = "rabbbit", t = "rabbit"
输出：3
解释：
如下所示, 有 3 种可以从 s 中得到 "rabbit" 的方案。
rabbbit
rabbbit
rabbbit

示例 2：

1
2
3
4
5
6
7
8
9
输入：s = "babgbag", t = "bag"
输出：5
解释：
如下所示, 有 5 种可以从 s 中得到 "bag" 的方案。 
babgbag
babgbag
babgbag
babgbag
babgbag

提示：

  • 1 <= s.length, t.length <= 1000
  • s 和 t 由英文字母组成
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
    public int numDistinct(String s, String t) {
        int len1 = s.length();
        int len2 = t.length();
        int[][] dp = new int[len1+1][len2+1];
        /*
         * dp[i][j]表示以j-1结尾的字符串 在i-1结尾的字符串中出现的个数
         *  0 就表示空字符串，在任何子串中都能出现
         */
        for (int i = 1; i <= len1; i++) {
            dp[i][0] = 1;
        }
        dp[0][0] = 1;

        for(int i = 1; i <= len1; i++) {
            for (int j = 1; j<= len2; 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[len1][len2] % 1000000007;
    }
}

37、两个字符串的删除操作 583

https://leetcode.cn/problems/delete-operation-for-two-strings/description/

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

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

示例 1：

1
2
3
输入: word1 = "sea", word2 = "eat"
输出: 2
解释: 第一步将 "sea" 变为 "ea" ，第二步将 "eat "变为 "ea"

示例 2:

1
2
输入：word1 = "leetcode", word2 = "etco"
输出：4

提示：

  • 1 <= word1.length, word2.length <= 500
  • word1 和 word2 只包含小写英文字母
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    public int minDistance(String word1, String word2) {
        // 找出两个串的最长公共子串的长度，然后用各自减去最长公共子串的长度
        int len1 = word1.length();
        int len2 = word2.length();

        int[][]dp = new int[len1+1][len2+1];
        for (int i = 1; i <= len1; i++) {
            for (int j = 1 ; j <= len2; j++) {
                if (word1.charAt(i-1) == word2.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]);
                }
            }
        }
        int length = dp[len1][len2];
        return len1+len2-2*length;
        
    }
}

38、编辑距离 72

https://leetcode.cn/problems/edit-distance/description/

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

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

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

示例 1：

1
2
3
4
5
6
输入：word1 = "horse", word2 = "ros"
输出：3
解释：
horse -> rorse (将 'h' 替换为 'r')
rorse -> rose (删除 'r')
rose -> ros (删除 'e')

示例 2：

1
2
3
4
5
6
7
8
输入：word1 = "intention", word2 = "execution"
输出：5
解释：
intention -> inention (删除 't')
inention -> enention (将 'i' 替换为 'e')
enention -> exention (将 'n' 替换为 'x')
exention -> exection (将 'n' 替换为 'c')
exection -> execution (插入 'u')

提示：

  • 0 <= word1.length, word2.length <= 500
  • word1 和 word2 由小写英文字母组成
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
class Solution {
    public int minDistance(String word1, String word2) {
        int len1 = word1.length();
        int len2 = word2.length();
        
        /* 
         * dp[i][j],表示将i-1这个字符结尾的字符串，转化为以j-1这个字符结尾的字符串需要的最小操作数
         * 
         */
        int[][] dp = new int[len1+1][len2+1];

        // 初始化 
        dp[0][0] = 0;
        // 删除该字符，word1有多少个删除多少个，才能让word1变为word2
        for (int i = 1; i <= len1; i++) {
            dp[i][0] = i;
        }
        // 增加对应的字符，word2有多少字符，word1就要增加多少个字符
        for (int j = 1; j <= len2; j++) {
            dp[0][j] = j;
        }
        // 状态转移

        for (int i = 1; i <= len1; i++) {
            for (int j = 1; j <= len2; j++) {
                if (word1.charAt(i-1) == word2.charAt(j-1)) {
                    dp[i][j] = dp[i-1][j-1];
                }else {
                    /*
                     * 1.增 word1在和word2不相等的地方 (i,j)，增加一个字符从而使得二者相等，等价于 dp[i][j-1] + 1;  
                     * 2.删 word1在和word2不相等的地方 (i,j)，删除一个字符从而使得二者相等，等价于 dp[i-1][j] + 1;
                     * 3.替换 word1在和word2不相等的地方 (i,j)，修改一个字符从而使得二者相等，等价于 dp[i-1][j-1] + 1;
                     * 取三者操作的最小值
                     */
                    dp[i][j] = Math.min(Math.min(dp[i][j-1] + 1, dp[i-1][j] + 1), dp[i-1][j-1] + 1);
                }
            }
        }
        return dp[len1][len2];
    }
}

39、回文子串 647

https://leetcode.cn/problems/palindromic-substrings/description/

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

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

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

示例 1：

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

示例 2：

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

提示：

  • 1 <= s.length <= 1000
  • s 由小写英文字母组成
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution {
    public int countSubstrings(String s) {
        /*
         * dp数组的定义，dp[i][j]表示左闭右闭的范围内的字符串是回文子串
         * 当s.charAt(i) == s.charAt(j)的时候，如果dp[i+1][j-1]也是回文子串，那么它就为回文子串
         * 将其想象成平面一直线的范围
         * 遍历的时候再考虑是二维数组，从左下角开始遍历
         */
        int len = s.length();
        int result = 0;
        boolean[][] dp = new boolean[len][len];
        for (int i = len-1; i >= 0; i--) {
            for (int j = i; j < len; j++) {
                if (s.charAt(i) == s.charAt(j)) {
                    if (j - i < 2) {
                        dp[i][j] = true;
                        result++;
                    }else {
                        if(dp[i+1][j-1]) {
                            dp[i][j] = true;
                            result++;
                        } 
                    }

                }
            }
        }
        return result;
    }
}

40、最长回文子序列 516

https://leetcode.cn/problems/longest-palindromic-subsequence/description/

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

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

示例 1：

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

示例 2：

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

提示：

  • 1 <= s.length <= 1000
  • s 仅由小写英文字母组成
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
    public int longestPalindromeSubseq(String s) {
        int len = s.length();

        int[][] dp = new int[len][len];
        
        /*
         * dp[i][j]表示的含义是，i~j范围内的最长回文子序列的个数，
         * 如果i和j表示的字符相同时，如果i和j的范围相差0，dp[i][j] = 1;
         * dp[i][j] = dp[i+1][j-1] + 2
         * 
         */
        for (int i = 0 ; i < len; i++) {
            dp[i][i] = 1;
        }
        for (int i = len - 1; i >= 0; i--) {
            for (int j = i+1; j < len; j++) {
                if (s.charAt(i) == s.charAt(j)) {
                    dp[i][j] = dp[i+1][j-1] + 2;
                } else {
                    dp[i][j] = Math.max(dp[i+1][j],dp[i][j-1]);
                }
            }
        }
        return dp[0][len-1];
    }
}

leetcode-动态规划

http://example.com/2024/11/17/leetcode-动态规划/

作者

John Doe

发布于

2024-11-17

更新于

2025-02-28

许可协议

You need to set install_url to use ShareThis. Please set it in _config.yml.

喜欢这篇文章？打赏一下作者吧

You forgot to set the business or currency_code for Paypal. Please set it in _config.yml.

评论

You forgot to set the shortname for Disqus. Please set it in _config.yml.
关注我

链接

分类

最新文章

归档

标签

hexo1
leetcode6
实验室区块链2
碎语1

订阅更新

You need to set client_id and slot_id to show this AD unit. Please set it in _config.yml.

follow.it

×