IVN
0%

动态规划

Posted on Edited on In
Symbols count in article: 26k Reading time ≈ 23 mins.

Dynamic Programming 选编

算法的优化就是这么一个过程:

  1. 先写出可读性很好的暴力递归算法

  2. 然后尝试运用动态规划技巧优化重叠子问题

  3. 最后尝试用空间压缩技巧优化空间复杂度

代码随想录

746. Min Cost Climbing Stairs

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public class LeetCode746 {
    public int minCostClimbingStairs(int[] cost) {
        //dp[n]=min(dp[n-1]+cost[n-1],dp[n-2]+cost[n-2])
        int a=0; //dp[0]
        int b=0; //dp[1]
        int c=0;
        for (int i = 2; i <= cost.length; i++) {
            c=Math.min(a+cost[i-2],b+cost[i-1]);
            a=b;
            b=c;
        }
        return c;
    }
}

343. Integer Break

1
2
3
4
5
6
7
8
9
10
11
12
public class LeetCode343 {
    public int integerBreak(int n) {
        int[] dp=new int[n+1];
        dp[2]=1;
        for (int i = 3; i <= n; i++) {
            for (int j = 2; j < i; j++) {
                dp[i]=Math.max(dp[i],Math.max(dp[j]*(i-j),j*(i-j)));
            }
        }
        return dp[n];
    }
}

96. Unique Binary Search Trees

1
2
3
4
5
6
7
8
9
10
11
12
13
public class LeetCode96 {
    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 = i-1; j >= 0; j--) {
                dp[i]+=dp[j]*dp[i-1-j];
            }
        }
        return dp[n];
    }
}

01背包问题

https://programmercarl.com/%E8%83%8C%E5%8C%85%E7%90%86%E8%AE%BA%E5%9F%BA%E7%A1%8001%E8%83%8C%E5%8C%85-1.html

先遍历物品还是先遍历背包容量？

labuladong

https://labuladong.github.io/algo/3/23/68/

dp关键词：

  • 核心思想：穷举求最值
  • 存在重叠子问题：引入备忘录或dp数组，避免不必要的计算
  • 具备最优子结构：
    • 要符合「最优子结构」，子问题间必须互相独立
  • 明确 base case -> 明确「状态」-> 明确「选择」 -> 定义 dp 数组/函数的含义

322. Coin Change

那么，既然知道了这是个动态规划问题，就要思考如何列出正确的状态转移方程？

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

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

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

4、明确 dp 函数/数组的定义。我们这里讲的是自顶向下的解法，所以会有一个递归的 dp 函数，一般来说函数的参数就是状态转移中会变化的量，也就是上面说到的「状态」；函数的返回值就是题目要求我们计算的量。就本题来说，状态只有一个，即「目标金额」，题目要求我们计算凑出目标金额所需的最少硬币数量。

所以我们可以这样定义 dp 函数：dp(n) 表示，输入一个目标金额 n，返回凑出目标金额 n 所需的最少硬币数量。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public class LeetCode322 {
    public int coinChange(int[] coins, int amount) {
        //dp[n]表示amount=n时，所需最少coin数
        int[] dp=new int[amount+1]; //0~amount
        Arrays.fill(dp,amount+1);
        dp[0]=0;
        for (int i = 1; i < dp.length; i++) {
            for (int coin : coins) {
                if(i<coin){
                    continue;
                }
                dp[i]=Math.min(dp[i],dp[i-coin]+1);
            }
        }
        return dp[amount]==amount+1 ? -1 : dp[amount];
    }
}

300. Longest Increasing Subsequence

法一：brute force O(N^2)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public int lengthOfLIS(int[] nums) {
    //dp[i] 以i结尾的increasing subsequence的最大长度
    //dp[i]=max(dp[j])+1,if j<i && nums[i]>nums[j]
    int[] dp=new int[nums.length];
    dp[0]=1;
    int max=1;
    for (int i = 1; i < nums.length; i++) {
        dp[i]=1;
        for(int j = 0 ; j < i ; j++){
            if(nums[j]<nums[i]){
                dp[i]=Math.max(dp[j]+1,dp[i]);
            }
        }
        max=Math.max(max,dp[i]);
    }
    return max;
}

法二：binary serach O(NlogN)

patience sort

牌的堆数就是最长递增子序列的长度

https://labuladong.github.io/algo/3/23/69/

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
public int lengthOfLIS(int[] nums) {
    //寻找左侧边界的二分搜索 [left,right)左闭右开区间搜索
    int[] top=new int[nums.length];
    top[0]=nums[0];
    int pile=1;
    for (int i = 1; i < nums.length; i++) {
        int left=0;
        int right=pile;
        while(left<right){//[left,right)
            int mid=left+(right-left)/2;
            if(top[mid]>nums[i]){
                right=mid;
            }else if(top[mid]<nums[i]){
                left=mid+1;
            }else{//注意此处逻辑，midVal==target不停止，继续缩小右侧边界，直到left==right
                right=mid;
            }
        }
        //退出循环时,leftVal==target(查找)或left是第一个比target大的元素
        top[left]=nums[i];
        if(left==pile){
            pile++;
        }
    }
    return pile;
}

354. Russian Doll Envelopes

先对宽度 w 进行升序排序，如果遇到 w 相同的情况，则按照高度 h 降序排序；之后把所有的 h 作为一个数组，在这个数组上计算 LIS 的长度就是答案。

注意：暴力搜索会超时，必须二分搜索！

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
public int maxEnvelopes(int[][] envelopes) {
    Arrays.sort(envelopes, new Comparator<int[]>() {
        @Override
        public int compare(int[] o1, int[] o2) {
            return o1[0]!=o2[0] ? o1[0]-o2[0] : o2[1]-o1[1];
        }
    });
    int[] top=new int[envelopes.length];
    top[0]=envelopes[0][1];
    int pile=1;
    for (int i = 1; i < envelopes.length; i++) {
        int target=envelopes[i][1];
        int left=0;
        int right=pile;
        while(left<right){
            int mid=left+(right-left)/2;
            if(top[mid]>target){
                right=mid;
            }else if(top[mid]<target){
                left=mid+1;
            }else{
                right=mid;
            }
        }
        top[left]=target;
        if(left==pile){
            pile++;
        }
    }
    return pile;
}

494. Target Sum

法一：backtracking

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public class LeetCode494 {
    int count;
    public int findTargetSumWays(int[] nums, int target) {
        count=0;
        backtracking(nums,target,0);
        return count;
    }

    void backtracking(int[] nums, int target, int i){
        if(i==nums.length){
            if(target==0){
                count++;
            }
            return;
        }
        backtracking(nums,target-nums[i],i+1); //+i
        backtracking(nums,target+nums[i],i+1); //-i
    }
}

注意：可以用memo优化

法二：dp

动态规划之所以比暴力算法快，是因为动态规划技巧消除了重叠子问题。

其实，这个问题可以转化为一个子集划分问题，而子集划分问题又是一个典型的背包问题。

首先，如果我们把 nums 划分成两个子集 A 和 B，分别代表分配 + 的数和分配 - 的数，那么他们和 target 存在如下关系：

1
2
3
4
sum(A) - sum(B) = target
sum(A) = target + sum(B)
sum(A) + sum(A) = target + sum(B) + sum(A)
2 * sum(A) = target + sum(nums)

综上，可以推出 sum(A) = (target + sum(nums)) / 2，也就是把原问题转化成：**nums 中存在几个子集 A，使得 A 中元素的和为 (target + sum(nums)) / 2**？

注意base case与416的不同！

  • 只问存不存在子集（划分）时:

    • dp[i] [0] = true, 用任意物品都能塞满0空间

    • j>0时，dp[0] [j] =false，用0个物品塞满大于0的空间，不可能

    • 至此 i=0 和 j=0 时都讨论完毕，i 和 j 都从 1 开始 dp

  • 问存在多少个子集（划分）时：

    • j=0 时 , 虽然用任意物品都能塞满0空间， 但不能确定总共有多少种可能， 除非同时 i=0

      • dp[0] [0] = 1, 用0个物品可以塞满0空间，有1种可能

    • j>0时，dp[0] [j] =0，用0个物品塞满大于0的空间，有0种可能

    • 至此，i=0 时讨论完毕，但 j=0 时未讨论完毕，i 从 1 开始，j 从 0 开始 dp

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
public int findTargetSumWays(int[] nums, int target) {
    //sumA-sumB=target
    //sumA=target+sumB
    //sumA+sumA=target+sumB+sumA
    //sumA=(target+sum)/2
    int sum=0;
    for (int num : nums) {
        sum+=num;
    }
    if(sum<Math.abs(target) ||  ((target+sum)&1)==1){
        return 0;
    }
    return subsetSum(nums,(target+sum)/2);
}

int subsetSum(int[] nums, int sum){
    int n=nums.length;
    int[][] dp=new int[n+1][sum+1];
    dp[0][0]=1; //base case: 没有物品可选，有一种情况能塞满0空间
    //base case: j>0时,dp[0][j]=0，因为没有物品可选，有0种情况能塞满j空间
    for (int i = 1; i <= n; i++) { //由于i=0时已讨论完毕，可以从i=1开始
        for (int j = 0; j <= sum; j++) { //j=0时并未讨论，j从0开始
            if(j-nums[i-1]>=0){
                dp[i][j]=dp[i-1][j]+dp[i-1][j-nums[i-1]];
            }else{
                dp[i][j]=dp[i-1][j];
            }
        }
    }
    return dp[n][sum];
}

法三： 压缩二维数组的dp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public int findTargetSumWays(int[] nums, int target) {
    target+= Arrays.stream(nums).sum();
    if(target%2==1 || target<0){
        return 0;
    }
    target/=2;
    int[] dp=new int[target+1];
    dp[0]=1;
    for (int num : nums) {
        //一定要倒序，这样才能保证较小部分untampered，代表前一行的值
        for (int j = target; j >=num; j--) {
            dp[j]+=dp[j-num];
        }
    }
    return dp[target];
}

72. Edit Distance

  • minimum number of operations
  • convert word1 to word2

解决两个字符串的动态规划问题，一般都是用两个指针 i, j 分别指向两个字符串的最后，然后一步步往前移动，缩小问题的规模。

  • 若字符相等，则skip
  • 若字符不等，则三选一：
    • insert
    • delete
    • replace

递归解法是自顶向下求解，DP table 是自底向上求解：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public class LeetCode72 {
    public int minDistance(String word1, String word2) {
        int s1=word1.length();
        int s2=word2.length();
        int[][] dp=new int[s1+1][s2+1];
        for (int i = 0; i <= s2; i++) {
            dp[0][i]=i;
        }
        for (int i = 0; i <= s1; i++) {
            dp[i][0]=i;
        }
        for (int i = 1; i <= s1; i++) {
            for (int j = 1; j <= s2; j++) {
                if(word1.charAt(i-1)==word2.charAt(j-1)){
                    dp[i][j]=dp[i-1][j-1];
                }else{
                    dp[i][j]=Math.min(Math.min(dp[i-1][j]+1,dp[i][j-1]+1),dp[i-1][j-1]+1);
                }
            }
        }

        return dp[s1][s2];
    }
}

174. Dungeon Game

minimum initial health

这道题的dp是倒序的，这点很重要，为什么不能像【最小路径和】一样是正序的？因为【最小路径和】是无状态的，你会发现【最小路径和】倒序dp也是可以的，这道题由于有“加血”的过程，只能依赖后面的值判断需要的血量。所以这里的dp [i] [j]表达的意思是：“从（i，j）出发，到达终点需要最少的血量”。因此，正序的含义为“从起点出发，到达位置（i，j）所需要的最少血量”；倒序的含义是“从（i，j）出发，到达终点需要最少的血量”。初始血量本来就是要求的，所以只能倒序dp

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
public class LeetCode174 {
    public int calculateMinimumHP(int[][] dungeon) {
        int row=dungeon.length;
        int col=dungeon[0].length;
        int[][] dp=new int[row][col];
        //dp[i][j]表示从i,j出发到达终点所需的最少血量
        dp[row-1][col-1]=dungeon[row-1][col-1]>=0 ? 1 : 1-dungeon[row-1][col-1];
        for (int i = row-2; i >= 0; i--) {
            dp[i][col-1]=dp[i+1][col-1]-dungeon[i][col-1];
            if(dp[i][col-1]<=0){
                dp[i][col-1]=1;
            }
        }
        for (int i = col-2; i >= 0; i--) {
            dp[row-1][i]=dp[row-1][i+1]-dungeon[row-1][i];
            if(dp[row-1][i]<=0){
                dp[row-1][i]=1;
            }
        }
        for (int i = row-2; i >= 0; i--) {
            for (int j = col-2; j >= 0; j--) {
                dp[i][j]=Math.min(dp[i+1][j],dp[i][j+1])-dungeon[i][j];
                if(dp[i][j]<=0){
                    dp[i][j]=1;
                }
            }
        }
        return dp[0][0];
    }
}

514. Freedom Trail

「状态」就是「当前需要输入的字符」和「当前圆盘指针的位置」。

「选择」就是「如何拨动指针得到待输入的字符」。

法一：

     * 定义转移方程：
     * dp[i][j] 代表到key[i]为止拼接所需要的最少步数，
     * 并且这个key[i]是第j个在圆盘上出现的key[i]

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
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
class Solution {
    public int findRotateSteps(String ring, String key) {
        /*
         * 贪心的算法：->举出了反例，是不正确的
         *
         * 最直观的转移方程：
         *
         * dp[i]: 代表到key[i]为止，拼接所需要的最少步数
         * dp[i-1]: 到key[i - 1]为止，拼接所需要的最少步数
         *
         * dp[i] = dp[i - 1] + (从key[i-1]到key[i]在圆盘上所要走的最短距离) + 1 （按button需要的步数为1）
         *
         * 下标x和下标y在圆盘上的最短距离： |x - y| 或者 n - |x - y|
         * 即Math.min(Math.abs(x - y), n - Math.abs(x - y))
         *
         * 但是，
         * key[i-1] 在圆盘上可以出现多次
         * key[i] 在圆盘上可以出现多次
         * 因此一个维度是不够的，再增加一个维度
         *
         * 定义转移方程：
         * dp[i][j] 代表到key[i]为止拼接所需要的最少步数，
         * 并且这个key[i]是第j个在圆盘上出现的key[i]
         *
         * 比如说key[i] = 'd'，在ring圆盘上出现位置的下标：2, 7, 8
         * dp[i][0] 代表到key[i]为止拼接所需要的最少步数，并且这个key[i]是位于下标位置为2的key[i]
         * dp[i][1] 代表到key[i]为止拼接所需要的最少步数，并且这个key[i]是位于下标位置为7的key[i]
         * ...以此类推
         *
         * 上一个字符是key[i-1] = 'a'，在ring圆盘上出现的位置下标是: 4, 9
         * dp[i][0] 代表到key[i - 1]为止拼接所需要的最少步数，并且这个key[i - 1]是位于下标位置为4的key[i]
         * dp[i][1] 代表到key[i - 1]为止拼接所需要的最少步数，并且这个key[i - 1]是位于下标位置为9的key[i]
         *
         * dp[i][j] =
         * Math.min(
         * dp[i-1][0] + 上一个字符key[i-1]（第0个出现的key[i - 1]）到这一个字符key[i]（第j个出现的key[i]）的最短距离,
         * dp[i-1][1] + 上一个字符key[i-1]（第1个出现的key[i - 1]）到这一个字符key[i]（第j个出现的key[i]）的最短距离,
         * ....
         * dp[i-1][k] + 上一个字符key[i-1]（第k个出现的key[i - 1]）到这一个字符key[i]（第j个出现的key[i]）的最短距离,
         * )  + 1 (按button的步数为1)
         * */

        char[] ringChar = ring.toCharArray();
        char[] keyChar = key.toCharArray();

        ArrayList<Integer>[] lists = new ArrayList[26];// an array of ArrayList<Integer>

        for (int i = 0; i < 26; i++) {//[0,25], represents every lowercase letter 
            lists[i] = new ArrayList<>();
        }

        // 遍历ring，存储每个字符出现的位置，即下标

        int n = ringChar.length, m = keyChar.length;

        for (int i = 0; i < n; i++) {
            char c = ringChar[i];
            // 找到对应的arraylist，存储下标
            lists[c - 'a'].add(i);
        }

        // ring 和 key的长度最多100，所以定个101很安全
        int[][] dp = new int[m][101];

        // dp[0][j] 只需要计算从12点方向到key[0]所需要走的最短距离

        for (int j = 0; j < lists[keyChar[0] - 'a'].size(); j++) {

            // 每一个key[0]字符所在的下标
            int x = lists[keyChar[0] - 'a'].get(j);

            // 第一个12点方向的字符的下标，其实就是0
            int y = lists[ringChar[0] - 'a'].get(0);

            dp[0][j] = Math.min(Math.abs(x - y), n - Math.abs(x - y)) + 1;
        }

        for (int i = 1; i < keyChar.length; i++) {

            // 列出当前的字符，和上一个的字符分别是什么
            char cur = keyChar[i], pre = keyChar[i - 1];

            for (int j = 0; j < lists[cur - 'a'].size(); j++) {
                // 当前字符cur出现在ring圆盘上每一个位置的下标
                int x = lists[cur - 'a'].get(j);

                int minSteps = Integer.MAX_VALUE;

                for (int k = 0; k < lists[pre - 'a'].size(); k++) {

                    // 上一个字符pre出现在ring圆盘上每一个位置的下标
                    int y = lists[pre - 'a'].get(k);

                    int steps = dp[i - 1][k] + Math.min(Math.abs(x - y), n - Math.abs(x - y)) + 1;

                    minSteps = Math.min(minSteps, steps);
                }

                dp[i][j] = minSteps;
            }
        }

        // dp[keyChar.length - 1][0], .... dp[keyChar.length - 1][k] 中的最小值，就是最终拼接key所需要的最少步数

        int ans = Integer.MAX_VALUE;
        for (int k = 0; k < 101; k++) {
            // 当等于0时，说明已经越界了，直接跳出循环
            if (dp[keyChar.length - 1][k] == 0) break;
            ans = Math.min(ans, dp[keyChar.length - 1][k]);
        }

        return ans;

    }

}
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
public class LeetCode514 {
    public int findRotateSteps(String ring, String key) {
        int n1=ring.length();
        int n2=key.length();
        List<Integer>[] lists=new ArrayList[26];
        for (int i = 0; i < lists.length; i++) {
            lists[i]=new ArrayList<>();
        }
        char[] rings = ring.toCharArray();
        for (int i = 0; i < n1; i++) {
            char c=rings[i];
            lists[c-'a'].add(i);
        }

        char[] keys = key.toCharArray();
        int[][] dp=new int[n2][101];
        for (int i = 0; i < lists[keys[0] - 'a'].size(); i++) {
            int pre=0;
            int cur=lists[keys[0]-'a'].get(i);
            dp[0][i]=dist(n1,pre,cur)+1;
        }


        for (int i = 1; i < n2; i++) {
            char curKey=keys[i];
            char preKey=keys[i-1];
            for (int j = 0; j < lists[curKey - 'a'].size(); j++) {
                int cur=lists[curKey-'a'].get(j);
                int min=Integer.MAX_VALUE;
                for (int k = 0; k < lists[preKey - 'a'].size(); k++) {
                    int pre=lists[preKey-'a'].get(k);
                    int cost=dp[i-1][k]+dist(n1,pre,cur)+1;
                    min=Math.min(min,cost);
                }
                dp[i][j]=min;
            }
        }

        int res=Integer.MAX_VALUE;
        for (int i = 0; i < 101; i++) {
            if(dp[n2-1][i]==0){
                break;
            }
            res=Math.min(res,dp[n2-1][i]);
        }
        return res;
    }

    int dist(int n1,int pre,int cur){
        return Math.min(Math.abs(pre-cur),n1-Math.abs(pre-cur));
    }
}

House Robber

198. House Robber

1
2
3
4
5
6
7
8
9
10
11
12
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-1],dp[i-2]+nums[i]);
    }
    return dp[nums.length-1];
}

优化空间复杂度后：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public int rob(int[] nums) {
    if(nums.length==1){
        return nums[0];
    }else if(nums.length==2){
        return Math.max(nums[0],nums[1]);
    }
    int a=nums[0];
    int b=Math.max(nums[0],nums[1]);
    int c=0;
    for (int i = 2; i < nums.length; i++) {
        c=Math.max(b,a+nums[i]);
        a=b;
        b=c;
    }
    return c;
}

213. House Robber II

由于0和n-1不可以同时取，只需取 0 ~ n-2 和 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
public class LeetCode213 {
    public int rob(int[] nums) {
        int n=nums.length;
        if(n==1){
            return nums[0];
        }if(n==2){
            return Math.max(nums[0],nums[1]);
        }
        return Math.max(helper(nums,0,n-2),helper(nums,1,n-1));

    }

    int helper(int[] nums,int start,int end){
        if(end-start==1){
            return Math.max(nums[start],nums[end]);
        }
        int a=nums[start];
        int b=Math.max(nums[start],nums[start+1]);
        int c=0;
        for (int i = start+2; i <= end; i++) {
            c=Math.max(a+nums[i],b);
            a=b;
            b=c;
        }
        return c;
    }
}

337. House Robber III

有意思：懂binary tree的小偷~

The thief has found himself a new place for his thievery again. There is only one entrance to this area, called root.

Besides the root, each house has one and only one parent house. After a tour, the smart thief realized that all houses in this place form a binary tree. It will automatically contact the police if two directly-linked houses were broken into on the same night.

Given the root of the binary tree, return the maximum amount of money the thief can rob without alerting the police.

法一：用memo记录

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public class LeetCode337 {
    Map<TreeNode,Integer> memo;
    public int rob(TreeNode root) {
        if(memo==null){
            memo=new HashMap<>();
        }
        if(root==null){
            return 0;
        }
        if(memo.containsKey(root)){
            return memo.get(root);
        }
        int rob_it=root.val+
                (root.left==null ? 0 : rob(root.left.left)+rob(root.left.right))+
                (root.right==null ? 0 : rob(root.right.left)+rob(root.right.right));
        int rob_it_not=rob(root.left)+rob(root.right);
        int result=Math.max(rob_it,rob_it_not);
        memo.put(root,result);
        return result;
    }
}

法二：不用memo记录

Best Time to Buy and Sell Stock

有限状态机 finite state machine

1
2
3
4
5
6
7
8
9
10
base case：
dp[0][j][0] = 0
dp[0][j][1] = -prices[0]
dp[i][0][0] = 0
dp[i][0][1] = -infinity  //不可能！
   

状态转移方程：
dp[i][k][0] = max(dp[i-1][k][0], dp[i-1][k][1] + prices[i])
dp[i][k][1] = max(dp[i-1][k][1], dp[i-1][k-1][0] - prices[i])

188. Best Time to Buy and Sell Stock IV

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
/*
解法1 动态规划
状态定义:
1. dp[i][k][0 or 1]
0 <= i <= n - 1, 1 <= k <= K
n 为天数，大 K 为交易数的上限，0 和 1 代表是否持有股票。
比如说 dp[3][2][1] 的含义就是：今天是第三天，我现在手上持有着股票，至今最多进行 2 次交易。
再比如 dp[2][3][0] 的含义：今天是第二天，我现在手上没有持有股票，至今最多进行 3 次交易
2. 最终要求的答案是 dp[n - 1][K][0]因为 dp[n - 1][K][1] 代表到最后一天手上还持有股票，
dp[n - 1][K][0] 表示最后一天手上的股票已经卖出去了，很显然后者得到的利润一定大于前者

basecase:
dp[0][j][0] = 0
解释：第0天不持有股票,不管交易次数限制多少次,同一天内交易与否,利润都为0

dp[0][j][1] = -prices[0]
解释：第0天持有股票,不管交易次数限制多少,最终利润都为-prices[0]

dp[i][0][0] = 0
解释：因为 k 是从 1 开始的，所以 k = 0 意味着根本不允许交易，这时候利润当然是 0。

dp[i][0][1] = -infinity
解释：不允许交易的情况下，是不可能持有股票的。
因为我们的算法要求一个最大值，所以初始值设为一个最小值，方便取最大值。

状态转移:
注意 k 的限制，在选择 buy 的时候相当于开启了一次交易，那么对于昨天来说，交易次数的上限 k 应该减小 1。

dp[i][k][0] = max(dp[i-1][k][0], dp[i-1][k][1] + prices[i])
              max( 今天选择 reset,        今天选择 sell       )
解释：今天我没有持有股票，有两种可能，我从这两种可能中求最大利润：
1. 我昨天就没有持有，且截至昨天最大交易次数限制为 k；然后我今天选择 rest，
所以我今天还是没有持有，最大交易次数限制依然为 k。
2. 我昨天持有股票，且截至昨天最大交易次数限制为 k；但是今天我 sell 了，
所以我今天没有持有股票了，最大交易次数限制依然为 k。

dp[i][k][1] = max(dp[i-1][k][1], dp[i-1][k-1][0] - prices[i])
              max( 今天选择 reset,         今天选择 buy         )
解释：今天我持有着股票，最大交易次数限制为 k，那么对于昨天来说，有两种可能，
我从这两种可能中求最大利润
1. 我昨天就持有着股票，且截至昨天最大交易次数限制为 k；然后今天选择 rest，
所以我今天还持有着股票，最大交易次数限制依然为 k。
2. 我昨天本没有持有，且截至昨天最大交易次数限制为 k - 1；但今天我选择 buy，
所以今天我就持有股票了，最大交易次数限制为 k。

*/
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
public class LeetCode188 {
    public int maxProfit(int k, int[] prices) {
        //dp[i][j][0 or 1]
        //0<=i<=n-1 , 0<=j<=k
        //第i天，交易上限为j时的最大利润
        int n=prices.length;
        if(n==0){
            return 0;
        }
        int[][][] dp=new int[n][k+1][2];
        for (int i = 0; i < n ; i++) {
            dp[i][0][0]=0;
            dp[i][0][1]=Integer.MIN_VALUE; //允许交易次数为0，却持有股票，不可能!
        }
        for (int i = 0; i < n; i++) {
            for (int j = 1; j <= k; j++) {//交易上限从1开始
                if(i==0){
                    dp[i][j][0]=0; //不持有
                    dp[i][j][1]=-prices[0]; //持有
                }else{
                    dp[i][j][0]=Math.max(dp[i-1][j][0],dp[i-1][j][1]+prices[i]);
                    dp[i][j][1]=Math.max(dp[i-1][j][1],dp[i-1][j-1][0]-prices[i]);
                }
            }
        }
        return dp[n-1][k][0];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
/*
解法2 解法1的状态压缩
dp[i][j][0] = max(dp[i-1][j][0], dp[i-1][j][1]+prices[i])
dp[i][j][1] = max(dp[i-1][j][1], dp[i-1][j-1][0]-prices[i])
1. 根据状态转移方程可以发现如果不关心dp三维数组的第2和第3维,
其实dp[i]只和dp[i-1]相关.所以可以考虑将第1维优化掉
2. 第3维只有0和1两种状态也可以考虑把第3维和第2维互换,
然后用2个变量优化掉
最后只用2个长度为k+1的1维数组表示 dp
3. 本题中的k最大值可以达到10^9,因为n天最多只能进行n/2次交易
因此可以取k和n/2中的较小值作为k然后再进行动态规划

*/

121. Best Time to Buy and Sell Stock

由于只允许1次交易（一买一卖）,无需考虑交易维度

1
2
3
4
5
6
7
8
9
dp[i][1][0] = max(dp[i-1][1][0], dp[i-1][1][1] + prices[i])
dp[i][1][1] = max(dp[i-1][1][1], dp[i-1][0][0] - prices[i]) 
            = max(dp[i-1][1][1], -prices[i])
解释：k = 0 的 base case，所以 dp[i-1][0][0] = 0。

现在发现 k 都是 1，不会改变，即 k 对状态转移已经没有影响了。
可以进行进一步化简去掉所有 k：
dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i])
dp[i][1] = max(dp[i-1][1], -prices[i])

写法一：统一风格

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public class LeetCode121 {
    public int maxProfit(int[] prices) {
        //dp[n][k][0/1]
        //k=1
        int n=prices.length;
        int[][] dp=new int[n][2];
        dp[0][0]=0;
        dp[0][1]=-prices[0];
        for (int i = 1; i < n; 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[n-1][0];
    }
}

本质上是记录截至今日的最低买价，并每天判断是否更新最大利润

写法二：特殊情况

1
2
3
4
5
6
7
8
9
10
public int maxProfit(int[] prices) {
    int n=prices.length;
    int profit=Integer.MIN_VALUE;
    int min=prices[0];
    for (int i = 1; i < n; i++) {
        profit=Math.max(profit,prices[i]-min);
        min=Math.min(min,prices[i]);
    }
    return profit>0 ? profit : 0;
}

122. Best Time to Buy and Sell Stock II

允许无穷次交易，无需考虑交易次数维度

1
2
3
4
5
6
7
dp[i][k][0] = max(dp[i-1][k][0], dp[i-1][k][1] + prices[i])
dp[i][k][1] = max(dp[i-1][k][1], dp[i-1][k-1][0] - prices[i])
            = max(dp[i-1][k][1], dp[i-1][k][0] - prices[i])

我们发现数组中的 k 已经不会改变了，也就是说不需要记录 k 这个状态了：
dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i])
dp[i][1] = max(dp[i-1][1], dp[i-1][0] - prices[i])
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public class LeetCode122 {
    public int maxProfit(int[] prices) {
        //交易次数无限制
        int n=prices.length;
        int[][] dp=new int[n][2];
        dp[0][0]=0;
        dp[0][1]=-prices[0];
        //dp[i][j][0]=Math.max(dp[i-1][j][0],dp[i-1][j][1]+prices[i])
        //dp[i][j][1]=Math.max(dp[i-1][j][1],dp[i-1][j-1][0]-prices[i])
        //dp[i-1][j][0]=dp[i-1][j-1][0]
        for (int i = 1; i < n; 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[n-1][0];
    }
}

123. Best Time to Buy and Sell Stock III

k=2时的情况

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public class LeetCode123 {
    public int maxProfit(int[] prices) {
        int n= prices.length;
        int[][][] dp=new int[n][3][2];

        for (int i = 0; i < n; i++) {
            dp[i][0][0]=0;
            dp[i][0][1]=Integer.MIN_VALUE;
        }

        for (int i = 0; i < n; i++) {
            for (int j = 1; j <= 2; j++) {
                if(i==0){
                    dp[i][j][0]=0;
                    dp[i][j][1]=-prices[i];
                }else{
                    dp[i][j][0]=Math.max(dp[i-1][j][0],dp[i-1][j][1]+prices[i]);
                    dp[i][j][1]=Math.max(dp[i-1][j][1],dp[i-1][j-1][0]-prices[i]);
                }
            }
        }
        return dp[n-1][2][0];
    }
}

309. Best Time to Buy and Sell Stock with Cooldown

  • 卖了后不能第二天立刻买
  • 无限次买卖
1
2
3
dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i])
dp[i][1] = max(dp[i-1][1], dp[i-2][0] - prices[i])
解释：第 i 天选择 buy 的时候，要从 i-2 的状态转移，而不是 i-1 。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public class LeetCode309 {
    public int maxProfit(int[] prices) {
        //dp[i][j][0]=Math.max(dp[i-1][j][0],dp[i-1][j][1]+prices[i]);
        //dp[i][j][1]=Math.max(dp[i-1][j][1],dp[i-1][j-1][0]-prices[i]);
        int n= prices.length;
        int[][] dp=new int[n][2];
        dp[0][0]=0;
        dp[0][1]=-prices[0];
        for (int i = 1; i < n; i++) {
            if(i==1){
                dp[i][1]=Math.max(-prices[0],-prices[1]);
                dp[i][0]=Math.max(0,prices[1]-prices[0]);
            }else{
                dp[i][1]=Math.max(dp[i-1][1],dp[i-2][0]-prices[i]); //第i天选择buy，要从i-2转移
                dp[i][0]=Math.max(dp[i-1][0],dp[i-1][1]+prices[i]);
            }
        }
        return dp[n-1][0];
    }
}

714. Best Time to Buy and Sell Stock with Transaction Fee

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public class LeetCode714 {
    public int maxProfit(int[] prices, int fee) {
        //dp[i][j][0]=Math.max(dp[i-1][j][0],dp[i-1][j][1]+prices[i]);
        //dp[i][j][1]=Math.max(dp[i-1][j][1],dp[i-1][j-1][0]-prices[i]);
        int n=prices.length;
        int[][] dp=new int[n][2];
        dp[0][0]=0;
        dp[0][1]=-prices[0]-fee;
        for (int i = 1; i < n; 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[n-1][0];
    }
}

背包问题

状态：

  1. 背包容量w

  2. 可选择的物品n

dp[i][w] 的定义如下：对于前 i 个物品，当前背包的容量为 w，这种情况下可以装的最大价值是 dp[i][w]。

比如说，如果 dp[3][5] = 6，其含义为：对于给定的一系列物品中，若只对前 3 个物品进行选择，当背包容量为 5 时，最多可以装下的价值为 6。

dp[i][w] 表示：对于前 i 个物品（从 1 开始计数），当前背包的容量为 w 时，这种情况下可以装下的最大价值是 dp[i][w]。

  • 如果你没有把这第 i 个物品装入背包，那么很显然，最大价值 dp[i][w] 应该等于 dp[i-1][w]，继承之前的结果。

  • 如果你把这第 i 个物品装入了背包，那么 dp[i][w] 应该等于 val[i-1] + dp[i-1][w - wt[i-1]]。

416. Partition Equal Subset Sum

给一个可装载重量为 sum / 2 的背包和 N 个物品，每个物品的重量为 nums[i]。现在让你装物品，是否存在一种装法，能够恰好将背包装满？

根据这个定义，我们想求的最终答案就是 dp[N][sum/2]，base case 就是 dp[..][0] = true 和 dp[0][..] = 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
public class LeetCode416 {
    public boolean canPartition(int[] nums) {
        int sum=0;
        for (int num : nums) {
            sum+=num;
        }
        if((sum&1)==1){
            return false;
        }
        sum/=2;
        int n=nums.length;
        boolean[][] dp=new boolean[n+1][sum+1];
        for (int i = 0; i <= n; i++) { //base case: 什么物品都不选，都能塞满0空间，dp[i][0]恒为true
            dp[i][0]=true;
        }
        //base case: j>0时,dp[0][j]恒为false,因为什么物品都没有却想塞满大于0的空间，不可能
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= sum; j++) {
                if(j-nums[i-1]<0){//不可能塞满负数大小的背包，第二项必定为false，值只取决于第一项
                    dp[i][j]=dp[i-1][j];
                }else{
                    dp[i][j]=dp[i-1][j] || dp[i-1][j-nums[i-1]];
                }
            }
        }
        return dp[n][sum]; //可否用前n个物品塞满sum
    }
}

518. Coin Change 2

注意：

  • 先 coin 后 amount，行！
  • 先 amount 后 coin，不行！

why? :

  • 纯完全背包是能凑成总和就行，不用管怎么凑的。

    本题是求凑出来的方案个数，是组合数，不允许重复。

  • 先 amount 后 coin, dp[0]至dp[i-1]都允许使用所有coin

  • 先 coin 后 amount, 每一层外层循环增加由新增的coin带来的新的组合方法数，可以避免重复！

1
2
3
4
5
6
7
8
9
10
11
12
13
public int change(int amount, int[] coins) {
    int[] dp=new int[amount+1];
    dp[0]=1;
    for(int coin : coins){ 
        for(int i=1; i<=amount; i++){
            if(i<coin){
                continue;
            }
            dp[i]+=dp[i-coin];
        }
    }
    return dp[amount];
}

子序列问题

1143. Longest Common Subsequence

当字符相等时：

当字符不等时：其中一个字符必定不在LCS中

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public class LeetCode1143 {
    public int longestCommonSubsequence(String text1, String text2) {
        int n1=text1.length();
        int n2=text2.length();
        int[][] dp=new int[n1+1][n2+1];
        for (int i = 1; i <= n1; i++) {
            for (int j = 1; j <= n2; j++) {
                if(text1.charAt(i-1)==text2.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]);
                }
            }
        }
        return dp[n1][n2];
    }
}

583. Delete Operation for Two Strings

法一：直接法，参考72. Edit Distance

删除s1中某一“冲突”字符，相当于在s2中插入该字符，都可以使s1、s2趋于相等

允许在s1、s2中删除字符，等价于：

  • 允许在s1中delete
  • 允许在s1中insert

使得s1与s2相等

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public class LeetCode583 {
    public int minDistance(String word1, String word2) {
        int n1=word1.length();
        int n2=word2.length();
        int[][] dp=new int[n1+1][n2+1];
        for (int i = 0; i <= n1; i++) {
            dp[i][0]=i;
        }
        for (int j = 0; j <= n2; j++) {
            dp[0][j]=j;
        }
        for (int i = 1; i <= n1; i++) {
            for (int j = 1; j <= n2; j++) {
                if(word1.charAt(i-1)==word2.charAt(j-1)){
                    dp[i][j]=dp[i-1][j-1];
                }else{
                    dp[i][j]=Math.min(dp[i-1][j]+1,dp[i][j-1]+1); //不能replace
                }
            }
        }
        return dp[n1][n2];
    }
}

法二：间接法，参考1143. Longest Common Subsequence

只能删不能换的话，两字符串最终变为它们的LCS时相等，只需得到它们的LCS的长度即可

712. Minimum ASCII Delete Sum for Two Strings

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public class LeetCode712 {
    public int minimumDeleteSum(String s1, String s2) {
        int n1=s1.length();
        int n2=s2.length();
        int[][] dp=new int[n1+1][n2+1];
        dp[0][0]=0;
        for (int i = 1; i <= n1; i++) {
            dp[i][0]=dp[i-1][0]+s1.charAt(i-1);
        }
        for (int j = 1; j <= n2; j++) {
            dp[0][j]=dp[0][j-1]+s2.charAt(j-1);
        }
        for (int i = 1; i <= n1; i++) {
            for (int j = 1; j <= n2; j++) {
                if(s1.charAt(i-1)==s2.charAt(j-1)){
                    dp[i][j]=dp[i-1][j-1];
                }else{
                    dp[i][j]=Math.min(dp[i-1][j]+s1.charAt(i-1),dp[i][j-1]+s2.charAt(j-1));
                }
            }
        }
        return dp[n1][n2];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public int minimumDeleteSum(String s1, String s2) {
    int n1=s1.length();
    int n2=s2.length();
    //longest common subsequence
    //largest common ascii sum
    //smallest uncommon ascii sum
    int[][] dp=new int[n1+1][n2+1];
    for (int i = n1-1; i >= 0; i--) {
        dp[i][n2]=dp[i+1][n2]+s1.charAt(i);
    }
    for (int j = n2-1; j >= 0; j--) {
        dp[n1][j]=dp[n1][j+1]+s2.charAt(j);
    }
    for(int i=n1-1; i>=0; i--){
        for(int j=n2-1; j>=0; j--){
            if(s1.charAt(i)==s2.charAt(j)){
                dp[i][j]=dp[i+1][j+1];
            }else{
                dp[i][j]=Math.min(dp[i+1][j]+s1.charAt(i),dp[i][j+1]+s2.charAt(j));
            }
        }
    }
    return dp[0][0];
}

Palindrome问题

516. Longest Palindromic Subsequence

想求 dp[i][j] 需要知道 dp[i+1][j-1]，dp[i+1][j]，dp[i][j-1] 这三个位置

最终结果在右上角

只需要填右上部分即可（对角线为base case, 1）

为了保证每次计算 dp[i][j]，左下方向的位置已经被计算出来，选择反着遍历：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public class LeetCode516 {
    public int longestPalindromeSubseq(String s) {
        int n=s.length();
        int[][] dp=new int[n][n];
        for (int i = n-1; i >= 0; i--) {
            dp[i][i]=1;
            for (int j = i+1; j < n; 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][n-1];
    }
}

1312. Minimum Insertion Steps to Make a String Palindrome

本题属于516. 最长回文子序列的子题，求的是将 s 变成回文串需要添加的最少字符数，所以我们只用求最长回文子序列长度即可，然后字符串 s 中除去最长回文子序列，剩下的字符就是不构成回文子序列的字符，添加与其同等数量的字符，将 s 构成回文串。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public class LeetCode1312 {
    public int minInsertions(String s) {
        //n - longest palindromic subsequence
        int n=s.length();
        int[][] dp=new int[n][n];
        for (int i = n-1; i >= 0; i--) {
            dp[i][i]=1;
            for (int j = i+1; j < n; 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 n-dp[0][n-1];
    }
}