LeetCode——动态规划（Java）

简介

记录一下自己刷题的历程以及代码。写题过程中参考了 代码随想录的刷题路线。会附上一些个人的思路，如果有错误，可以在评论区提醒一下。

[简单] 509. 斐波那契数

原题链接

简单的递归

public int fib(int n) {
    if(n == 0) return 0;
    else if(n == 1) return 1;
    else return fib(n - 1) + fib(n - 2);
}
1
2
3
4
5

动态规划

class Solution {
    public int fib(int n) {
        int[] dp = new int[n + 1];
        if(n >= 0) dp[0] = 0;
        if(n >= 1) dp[1] = 1;
        for(int i = 2; i <= n; i++){
            dp[i] = dp[i - 1] + dp[i - 2];
        }
        return dp[n];
    }
}
1
2
3
4
5
6
7
8
9
10
11

[简单] 70. 爬楼梯

原题链接

同斐波那契数一样

class Solution {
    public int climbStairs(int n) {
        int[] dp = new int[n + 1];
        if(n >= 1) dp[1] = 1;
        if(n >= 2) dp[2] = 2;
        for(int i = 3; i <= n; i++){
            dp[i] = dp[i - 1] + dp[i - 2];
        }
        return dp[n];
    }
}
1
2
3
4
5
6
7
8
9
10
11

[简单] 746. 使用最小花费爬楼梯

原题链接

class Solution {
    public int minCostClimbingStairs(int[] cost) {
        int length = cost.length;
        int[] dp = new int[length + 1];
        dp[0] = 0;
        dp[1] = 0;
        for(int i = 2; i <= length; i++){
            dp[i] = Math.min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]);
        }
        return dp[length];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12

[中等] 62. 不同路径

原题链接

先确定dp数组表示是每个网格有多少路径
机器人只能向下或者向右，这样的话推导式就是dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
第一行和第一列，因为只能选择一个方向，路径都是1，初始化dp时进行赋值。

class Solution {
    public int uniquePaths(int m, int n) {
        int[][] dp = new int[m][n];
        dp[0][0] = 0;
        for(int i = 0; i < m; i++){
            dp[i][0] = 1;
        }
        for(int i = 0; i < n; i++){
            dp[0][i] = 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];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

[中等] 63. 不同路径 II

原题链接

在上一题的基础中，做障碍判断
初始网格需要做判断，有可能在起点出现障碍而不可达
把第一行和第一列的逻辑改为dp[i][0] = dp[i - 1][0];，因为当出现障碍的时候，第一行或者第一列的网格是不可达的，

class Solution {
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        int m = obstacleGrid.length;
        int n = obstacleGrid[0].length;
        int[][] dp = new int[m][n];
        if(obstacleGrid[0][0] == 1) dp[0][0] = 0;
        else dp[0][0] = 1;
        for(int i = 1; i < m; i++){
            if(obstacleGrid[i][0] == 0)
                dp[i][0] = dp[i - 1][0];
        }
        for(int i = 1; i < n; i++){
            if(obstacleGrid[0][i] == 0)
                dp[0][i] = dp[0][i - 1];
        }
        for(int i = 1; i < m; i++){
            for(int j = 1; j < n; j++){
                if(obstacleGrid[i][j] == 1){
                    dp[i][j] = 0;
                    continue;
                }
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
            }
        }
        return dp[m - 1][n - 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

[中等] 343. 整数拆分

原题链接

dp数组保存的值是：正整数i拆分后的最大乘积
递推公式就是在循环中 将i拆解为两个数的和，找出不同组合中乘积最大的情况。

初始化的时候注意，dp[2] 以及 dp[3] 用自身值放入数组。

从下图可以知道，下标i == 2 或者 i == 3 的情况下，拆分成两个数以上的乘积值比本身小，意味着之后的数字中如果拆出了3，由于3继续拆分只会比本身更小，所以没有拆分必要。举个例子，手推这个过程的时候，比如10 = 3 + 7，理论上7 = 3 + 4，3与4的乘积大于7，所以最后10 = 3 + 3 + 4，但是3则没有继续拆分的必要。

手推一下这个过程比较容易理解

注意：如果想保证使用dp数组就能完成所有返回值，可以把 dp[j] 和 j 的大小判断逻辑加入到max的取值中进行判断。但我推导下来，会出现这种情况的其实只有2和3，所以我进行了单独设置。

class Solution {
    public int integerBreak(int n) {
        // 每个正整数可以化成的最大乘积
        int[] dp = new int[n + 1];
        if(n ==2) return 1;
        else if(n == 3) return 2;
        dp[2] = 2;
        if(n >= 3) dp[3] = 3;
        for(int i = 4; i <= n; i++){
            int max = Integer.MIN_VALUE;
            for(int j = i/2; j > 1; j--){
                int num = dp[j] * dp[i - j];
                max = num > max ? num : max;
            }
            dp[i] = max;
        }
        return dp[n];
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

[中等] 96. 不同的二叉搜索树

原题链接

dp数组表示的是 i 个结点有dp[ i ] 种摆放方法摆出二叉搜索树

递推式就是取 j 作为根节点，左边有 j - 1 个结点， 右边 有 i - j 个结点，二者的摆放方法数相乘即为：以j为根节点，节点[1, i] 的摆放方法数。

dp[ 0 ] 取值 为1主要是为了后续相乘时正确处理，也可以理解为， 0 个节点只有一种摆放方式，就是没得摆。

class Solution {
    public int numTrees(int n) {
        int[] dp = new int[n + 1];
        dp[0] = 1;
        dp[1] = 1;
        if(n >= 2) dp[2] = 2;
        for(int i = 3; i <= n; i++) {
            for(int j = 1; j <= i; j++){
                dp[i] += dp[i - j] * dp[j - 1];
            }
        }
        return dp[n];
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

背包问题

01背包

[中等] 416. 分割等和子集

原题链接

动态规划：01背包解法
数组总和 sum / 2 就是背包的最大容量，nums数组看做物品，重量和价值都是nums[ i ]，只要最后dp[dp.length - 1] == dp.length - 1就说明能够取到总和一半的组合

可以看一看代码随想录：一维背包中一维背包的设计思想，自己递推的时候脑袋里按照二维背包的思路去规划

dp数组表示：背包限制为i 的 情况下可以取到的最大总和
递推公式：不取当前数字，且限制为i 的最大总和 dp[ j ]。
取当前数字，限制为 i 的最大总和dp[j - nums[i]] + nums[i]，二者取最大值

二重循环中第一层循环是遍历[0 ,i]的物品允许取的情况，二层循环是背包总和限制为 j 的情况
内层循环需要保证倒序，因为使用一维数组的情况下，正序遍历会把上一层物品状态覆盖。

for(int i = 1; i < nums.length; i++){
            for(int j = dp.length - 1; j >= nums[i]; j--){
                dp[j] = Math.max(dp[j], dp[j - nums[i]] + nums[i]);
            }
        }
1
2
3
4
5

class Solution {
    public boolean canPartition(int[] nums) {
        int sum = 0;
        for(int i = 0; i < nums.length; i++)
            sum += nums[i];
        if(sum % 2 == 1) return false;
        int[] dp = new int[sum / 2 + 1];
        for(int i = 1; i < dp.length; i++){
            if(i >= nums[0]) dp[i] = nums[0];
        }
        //倒序遍历是保证每个数字只取一次
        for(int i = 1; i < nums.length; i++){
            for(int j = dp.length - 1; j >= nums[i]; j--){
                dp[j] = Math.max(dp[j], dp[j - nums[i]] + nums[i]);
            }
        }
        if(dp[dp.length - 1] == dp.length - 1) return true;
        return false;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

[中等] 1049. 最后一块石头的重量 II

原题链接

和上一题 [中等] 416. 分割等和子集 相像，其实就是找出两堆重量尽量相近的石头。

如果给出一个背包，最大容量为j，dp[j] 就是他能取到的最大石头重量和，dp数组最大下标为sum / 2，也就是一个石头堆：dp[dp.length - 1]就是这一半石头堆能够取到的最大重量。sum - dp[dp.length - 1]就是另一个石头堆，且若两个石头堆重量无法相等，后者一定比前者大，所以最后的返回值就是二者之差

class Solution {
    public int lastStoneWeightII(int[] stones) {
        int sum = 0;
        for(int i = 0; i < stones.length; i++)
            sum += stones[i];
        int[] dp = new int[sum / 2 + 1];
        for(int i = 1; i < dp.length; i++){
            if(i >= stones[0]) dp[i] = stones[0];
        }
        //倒序遍历是保证每个数字只取一次
        for(int i = 1; i < stones.length; i++){
            for(int j = dp.length - 1; j >= stones[i]; j--){
                dp[j] = Math.max(dp[j], dp[j - stones[i]] + stones[i]);
            }
        }
        return sum - dp[dp.length - 1] - dp[dp.length - 1];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

[中等] 494. 目标和

原题链接

class Solution {
    public int findTargetSumWays(int[] nums, int target) {
        int sum = 0;
        for(int i = 0; i < nums.length; i++){
            sum += nums[i];
        }
        //表示加法集合不是整数，也就是无法取到
        if((sum + target) % 2 != 0) return 0;
        //target 绝对值 大于 sum 同样无法取到
        if((Math.abs(target) > sum)) return 0;
        //表示数字总和取到 j 有dp[j]种方案
        int[] dp = new int[(sum +target) / 2 + 1];
        //target == 0，一个数都不取 为一种方案
        dp[0] = 1;
        //倒序遍历是保证每个数字只取一次
        for(int i = 0; i < nums.length; i++){
            for(int j = dp.length - 1; j >= nums[i]; j--){
                dp[j] += dp[j - nums[i]];
            }
        }
        return dp[dp.length - 1];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

[中等] 474. 一和零

原题链接

标准的01背包，只是对物品重量的考虑变成二维的。
dp表示：限制 i个0 和 j个1 情况下的最大子集长度
递推公式从二者取最大值：dp[ i ] [ j ] 表示不取当前物品，dp[i - zeroNum][j - oneNum] + 1表示取当前物品
对dp的遍历都是从后往前，因为都是对背包容量的遍历，不能覆盖先前值，把二维遍历对应到普通01背包的一维遍历即可

可以在考虑每个字符串时对dp数组做输出观察状态，更易于理解：

class Solution {
    public int findMaxForm(String[] strs, int m, int n) {
        // 限制 i个0 和 j个1 情况下的最大子集长度
        int[][] dp = new int[m + 1][n + 1];
        for(String str : strs){
            char[] chars = str.toCharArray();
            int zeroNum = 0;
            int oneNum = 0;
            for(char c : chars){
                if(c == '0')zeroNum++;
                else oneNum++;
            }
            for(int i = m; i >= zeroNum; i--){
                for(int j = n; j >= oneNum; j--){
                    dp[i][j] = Math.max(dp[i - zeroNum][j - oneNum] + 1, dp[i][j]);
                }
            }
            System.out.println("当前考虑字符串：" + str);
            for(int i = 0; i <= m; i++){
                for(int j = 0; j <=n ;j++){
                    System.out.print(dp[i][j] + " ");
                }
                System.out.println();
            }
            System.out.println();
        }
        return dp[m][n];
    }
}
public class main {
    public static void main(String[] args) {
        Solution solution = new Solution();
        System.out.println(solution.findMaxForm(new String[]{"10","0001","111001","1","0"}, 5, 3));
    }
}

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

完全背包

• 如果求组合数就是外层for循环遍历物品，内层for遍历背包。
  外层遍历物品，考虑过的物品不会再回头考虑，就不用考虑排序问题，每个组合都是唯一的。

• 如果求排列数就是外层for遍历背包，内层for循环遍历物品。

[中等] 518. 零钱兑换 II

原题链接

突然觉得和回溯法的题目很像，可以看看LeetCode——回溯算法(Java) 中39题，把里面的代码的返回值List<List<Integer>> ans输出size也能通过测试，但是在正式提交时回出现爆内存的情况，因为本题中是不需要具体方案，只需要给出方案数，这或许就是碰到一个题目是使用回溯还是动态规划的一个判断角度。

本题是一个完全背包，跟01背包的差距就是完全背包的物品不限制选取次数

dp数组表示：背包容量为 j 时，最多有dp[ j ] 种方案
递归公式：第二层对背包容量的遍历采用正序，因为区别于01背包，物品可以选择多次。

初始化时：
如果正好选了coins[i]后，也就是j-coins[i] == 0的情况表示这个硬币刚好能选，此时dp[0]为1表示只选coins[i]存在这样的一种选择，可以理解为amount == 0 时选择0个物品为1种方案。

class Solution {
    public int change(int amount, int[] coins) {
        int[]dp = new int[amount + 1];
        dp[0] = 1;
        for (int i = 0; i < coins.length; i++){
            for(int j = coins[i]; j <= amount; j++){
                dp[j] += dp[j - coins[i]];
            }
        }
        return dp[amount];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12

[中等] 377. 组合总和 Ⅳ

同上一题一样，可以和回溯法的题目一起思考，如果本题要把排列都列出来的话，只能使用回溯算法爆搜。本题就是求排列问题，所以外层循环为背包容量。

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

[中等] 322. 零钱兑换

原题链接

dp[j]：凑足总额为j所需钱币的最少个数为dp[j]

递推公式：dp[j]表示不考虑本次循环到的钱币，dp[j - coins[i]] + 1表示考虑一个coins[i]

初始化dp[i] = Integer.MAX_VALUE表示没有方法能够凑到总额j，也用于后续比较最小值被有方法的情况覆盖。

class Solution {
    public int coinChange(int[] coins, int amount) {
        int[]dp = new int[amount + 1];
        dp[0] = 0;
        for(int i = 1; i < dp.length; i++) dp[i] = Integer.MAX_VALUE;
        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;
        return dp[amount];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

[中等] 279. 完全平方数

原题链接

dp数组：和为 j 的完全平方数的最少数量为 dp[j]

递推公式：dp[ j ] 表示不考虑选当前数字 i * i 的取值数量，dp[j - i * i] + 1表示选取一个当前数字i * i 的取值数量，因为是完全背包问题，二层循环从前往后遍历，同一个数字可以多次选取

初始化，除了dp[ 0 ] 用于做最小值比较，并且本身题目 n 范围并不包括0，其余设置Integer.MAX_VALUE，用于被覆盖，因为 1 也属于完全平方数，所以最后的数组每个元素必定是有最小方案数的，不存在还有Integer.MAX_VALUE的情况

class Solution {
    public int numSquares(int n) {
        // 和为 j 的完全平方数的最少数量为 dp[j]
        int[] dp = new int[n + 1];
        dp[0] = 0;
        for(int j = 1; j <= n; j++){
            dp[j] = Integer.MAX_VALUE;
        }
        for(int i = 1; i <= 100; i++){
            for(int j = i * i; j <= n; j++){
                dp[j] = Math.min(dp[j], dp[j - i * i] + 1);
            }
        }
        return dp[n];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

[中等] 139. 单词拆分

原题链接

只是在基础的完全背包上添加了一些字符串操作

dp数组：从左到右长度为 j 的字符串的是否能够被表示 ，dp[j]为布尔值

递推公式：每一层容量考虑时都需要考虑wordDict中的所有字符串，所以，容量为外层循环，字符串集为内层循环，以 j 为末端的子串如果在wordDict集中，那么它是否能够被表示取决于[j - length]， length为子串长度。
并且如果当前层 dp[ j ] 已经为true，找到方案的情况下，就可以跳出本次循环。题目中并没有需要提供方案数。

初始化：dp[0]为true用于后续做判断

class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        boolean[] dp = new boolean[s.length() + 1];
        dp[0] = true;
        for(int j = 1; j <= s.length() ; j++){
            for(int i = 0; i < wordDict.size(); i++){
                int length = wordDict.get(i).length();
                if(j < length) continue;
                String str = s.substring(j - length, j);
                if(str.equals(wordDict.get(i))){
                    dp[j] = dp[j - length];
                    if(dp[j]) break;
                }
            }
        }
        return dp[s.length()];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

[中等] 198. 打家劫舍

原题链接

class Solution {
    public int rob(int[] nums) {
        // [0,j] 的 最大收益为 dp[j]
        int[] dp = new int[nums.length];
        dp[0] = nums[0];
        if(nums.length > 1) dp[1] = Math.max(nums[1], dp[0]);
        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];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12

[中等] 213. 打家劫舍 II

原题链接

有点讨巧的方法，调用函数保留线性打家劫舍的方案，调用时两种情况，不考虑头或者不考虑尾，强制把环形问题拆分为线性考虑。

class Solution {
    public int rob(int[] nums) {
        if(nums.length == 1) return nums[0];
        int result1 = rob(nums, 0, nums.length - 1);
        int result2 = rob(nums, 1, nums.length);
        return Math.max(result1, result2);
    } 

    public int rob(int[] nums, int start, int end) {
        int length = end - start;
        // [0,j] 的 最大收益为 dp[j]
        int[] dp = new int[nums.length];
        dp[start] = nums[start];
        if(length > 1) dp[start + 1] = Math.max(nums[start + 1], dp[start]);
        for(int i = start + 2; i < end; i++){
            dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i]);
        }
        return dp[end - 1];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

树形DP

[中等] 337. 打家劫舍 III

原题链接

可以设置二维dp数组保存遍历过的节点状态，但是由于本题只需要子树的状态，所以可以直接使用返回值，int[0] 表示偷窃当前节点, int[1]表示没有盗窃当前节点

class Solution {
    public int rob(TreeNode root) {
        int[] nums = recursion(root);
        return Math.max(nums[0], nums[1]);
    }

    // int[0] 表示偷窃当前节点, int[1]表示没有盗窃当前节点
    public int[] recursion(TreeNode root) {
        if(root == null) return new int[]{0 ,0};
        else if(root.left == null && root.right == null){
            return new int[]{root.val, 0};
        }
        int[] left = recursion(root.left);
        int[] right = recursion(root.right);

        // 偷窃当前节点
        int value0 = root.val + left[1] + right[1];
        // 不偷窃当前节点
        int value1 = Math.max(left[0], left[1]) + Math.max(right[0], right[1]);

        return new int[]{value0, value1};
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

[简单] 121. 买卖股票的最佳时机

原题链接

class Solution {
    public int maxProfit(int[] prices) {
        int[][] dp = new int[prices.length][2];
        //dp[j][0] 表示第j天持有股票的最大现金，dp[j][1]表示第j天不持有股票的最大现金；
        int result = 0;
        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];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

[中等] 122. 买卖股票的最佳时机 II

原题链接

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

[中等] 123. 买卖股票的最佳时机 III

原题链接

题目中有五种状态，用dp二维下标 [0, 4]表示，0 未买入，1 第一次买入， 2 第一次卖出， 3 第二次买入，4 第二次卖出。

初始化的时候，其实是代入了当天买入卖出，收益为0 这样的情况。最大的时候一定是卖出的状态，而两次卖出的状态现金最大一定是最后一次卖出。如果第一次卖出已经是最大值了，那么我们可以在当天立刻买入再立刻卖出。所以dp[prices.length - 1][4]已经包含了dp[prices.length - 1][2]的情况。也就是说第二次卖出手里所剩的钱一定是最多的。

其实通过观察动态转移方程可以发现，dp数组是可以压缩为一维的，不过那样写会比较绕，空间上会更节省资源

class Solution {
    public int maxProfit(int[] prices) {
        int[][] dp = new int[prices.length][5];
        // 0 未买入，1 第一次买入， 2 第一次卖出， 3 第二次买入，4 第二次卖出
        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 < prices.length; i++){
            dp[i][0] = dp[i - 1][0];
            dp[i][1] = Math.max(dp[i - 1][0] - prices[i], dp[i - 1][1]);
            dp[i][2] = Math.max(dp[i - 1][1] + prices[i], dp[i - 1][2]);
            dp[i][3] = Math.max(dp[i - 1][2] - prices[i], dp[i - 1][3]);
            dp[i][4] = Math.max(dp[i - 1][3] + prices[i], dp[i - 1][4]);
        }
        return dp[prices.length - 1][4];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

[中等] 188. 买卖股票的最佳时机 IV

原题链接

在 123. 买卖股票的最佳时机 III 的基础上做扩充就可以了，观察买卖两次的代码发现无非就是对奇数和偶数做区分

class Solution {
    public int maxProfit(int k, int[] prices) {
        int[][] dp = new int[prices.length][2 * k + 1];
        // 0 未买入，1 第一次买入， 2 第一次卖出， 3 第二次买入，4 第二次卖出
        for(int i = 0; i <= 2 * k; i++){
            if(i % 2 != 0) dp[0][i] = -prices[0];
        }
        for(int i = 1; i < prices.length; i++){
            for(int j = 1; j <= 2 * k; j++) {
                if(j % 2 == 0){
                    dp[i][j] = Math.max(dp[i - 1][j - 1] + prices[i], dp[i - 1][j]);
                }else{
                    dp[i][j] = Math.max(dp[i - 1][j - 1] - prices[i], dp[i - 1][j]);
                }
            }
        }
        return dp[prices.length - 1][2 * k];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

[中等] 309. 买卖股票的最佳时机含冷冻期

原题链接

四种状态：0 未持有股票， 1 买入， 2 卖出， 3表冷冻期

注意0表示的是非冷冻期可操作情况下选择不操作
0：今天不持有股票，昨天也不持有，或者昨天是冷冻期
1：今天买入，昨天不会是卖出，但是需要比较一下是今天买入好还是之前的买入好
2：今天卖出，昨天不能是冷冻期，也不能是卖出
3：今天冷冻期，昨天就是卖出股票

最后得到的最大值，有可能最后一天是没做任何操作，或者最后一天是冷冻期，也有可能最后一天出售的股票，所以需要进行比较

class Solution {
    public int maxProfit(int[] prices) {
        int[][] dp = new int[prices.length][4];
        //0 未持有股票， 1 买入， 2 卖出， 3表冷冻期
        dp[0][0] = 0;
        dp[0][1] = -prices[0];
        dp[0][2] = 0;
        dp[0][3] = 0;
        for(int i = 1; i < prices.length; i++){
            // 今天不持有股票, 昨天也不持有，或者昨天冷冻期（冷冻期另外算）
            dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][3]);
            // 今天买入，昨天不会是卖出
            int max = Math.max(dp[i - 1][3], dp[i - 1][0]) - prices[i];
            dp[i][1] = Math.max(dp[i - 1][1], max);
            // 今天卖出，昨天不能是冷冻期，也不能是卖出
            dp[i][2] = dp[i - 1][1] + prices[i];
            // 今天冷冻期，昨天卖出
            dp[i][3] = dp[i - 1][2];
        }
        int max = Math.max(dp[prices.length - 1][0], dp[prices.length - 1][2]);
        return Math.max(dp[prices.length - 1][3], max);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

[中等] 714. 买卖股票的最佳时机含手续费

原题链接

和 [中等] 122. 买卖股票的最佳时机 II没什么区别，卖出的时候把手续费算上即可

class Solution {
    public int maxProfit(int[] prices, int fee) {
        int[][] dp = new int[prices.length][2];
        //dp[0] 表示第i - 1不持有股票的最大现金，dp[1]表示第i- 1天持有股票的最大现金；
        dp[0][0] = 0;
        dp[0][1] = -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] - fee);
            //当天持有股票 = 昨天持有股票 || 昨天不持有股票 - 今天股票成本
            dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] - prices[i]);
        }
        return dp[prices.length - 1][0];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

[中等] 300. 最长递增子序列

原题链接

dp[i] 表示以 nums[i] 为结尾的最大递增子序列个数

class Solution {
    public int lengthOfLIS(int[] nums) {
        // 以 nums[i] 为结尾的最大递增子序列个数
        int[] dp = new int[nums.length];
        for(int i = 0; i < nums.length; i++)
            dp[i] = 1;
        for(int i = 1; i <nums.length; i++){
            for(int j = 0; j < i; j++){
                if(nums[i] > nums[j])
                    dp[i] = Math.max(dp[i], dp[j] + 1);
            }
        }
        int max = Integer.MIN_VALUE;
        for(int i = 0; i < nums.length; i++){
            max = Math.max(dp[i], max);
        }
        return max;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

[简单] 674. 最长连续递增序列

原题链接

dp[i] 表示以 nums[i] 为结尾的最大连续递增子序列个数，在遍历nums时，就不需要开二重循环，因为递增序列要求连续，只需要跟前一个数字做比较即可

观察代码会发现，每一次dp[i] = Math.max(dp[i], dp[i - 1] + 1)只用到了前一位的dp状态，可以考虑将数组压缩

class Solution {
    public int findLengthOfLCIS(int[] nums) {
        // 以 nums[i] 为结尾的最大连续递增子序列个数
        int[] dp = new int[nums.length];
        for(int i = 0; i < nums.length; i++)
            dp[i] = 1;
        int max = dp[0];
        for(int i = 1; i <nums.length; i++){
            if(nums[i] > nums[i- 1])
                dp[i] = Math.max(dp[i], dp[i - 1] + 1);
            max = Math.max(dp[i], max);
        }
        return max;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

[中等] 718. 最长重复子数组

原题链接

dp[i][j] 表示：以 nums1[i] 为结尾，以nums2[j] 为结尾的最大重复子串长度 为 dp[i][j]

dp[i][j] = dp[i - 1][j - 1] + 1;相当于回退去找i 和 j 的前一位，看是否相等，并得到最大重复子串长度，如果nums1[i - 1] != nums2[j - 1]，dp[i - 1][j - 1] == 0，dp[i][j]即为1

class Solution {
    public int findLength(int[] nums1, int[] nums2) {
        // 以 nums1[i] 为结尾，以nums2[j] 为结尾的最大重复子串长度 为 dp[i][j]
        int[][] dp = new int[nums1.length][nums2.length];
        int max = Integer.MIN_VALUE;
        for(int i = 0; i < nums1.length; i++){
            if(nums1[i] == nums2[0]) dp[i][0] = 1;
            if(max < dp[i][0]) max = dp[i][0];
        }
        for(int i = 0; i < nums2.length; i++){
            if(nums2[i] == nums1[0]) dp[0][i] = 1;
            if(max < dp[0][i]) max = dp[0][i];
        }

        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;
                if(max < dp[i][j]) max = dp[i][j];
            }
        }
        return max;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

[中等] 1143. 最长公共子序列

原题链接
dp[i][j] 表示： char1[0, i]与char2[0, j] 的最大重复子串长度

class Solution {
    public int longestCommonSubsequence(String text1, String text2) {
        char[] char1 = text1.toCharArray();
        char[] char2 = text2.toCharArray();
        // 以 char1[i] 为结尾，以char2[j] 为结尾的最大重复子串长度 为 dp[i][j]
        int[][] dp = new int[char1.length][char2.length];
        if(char1[0] == char2[0]) dp[0][0] = 1;
        int max = dp[0][0];
        for(int i = 1; i < char1.length; i++){
            if(char1[i] == char2[0]) dp[i][0] = 1;
            else dp[i][0] = dp[i - 1][0];
            if(max < dp[i][0]) max = dp[i][0];
        }
        for(int i = 1; i < char2.length; i++){
            if(char2[i] == char1[0]) dp[0][i] = 1;
            else dp[0][i] = dp[0][i - 1];
            if(max < dp[0][i]) max = dp[0][i];
        }

        for(int i = 1; i < char1.length; i++){
            for(int j = 1; j < char2.length; j++){
                if(char1[i] == char2[j]) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                }else{
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
                }
                if(max < dp[i][j]) max = dp[i][j];
            }
        }
        return max;
    }
}
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