【力扣刷题】Day29——DP专题

---

五、ababa…

上一篇文章：【力扣刷题】Day28——DP专题_塔塔开!!!的博客-CSDN博客

20. 打家劫舍

题目链接：198. 打家劫舍 - 力扣（LeetCode）

思路：动态规划

我们可以分为两种情况，偷或者不偷，取两种情况的最值即可，可做出如下讨论：

• 当只有一户人家时，我们必偷
• 当只有两户人家时，我们偷最有钱的那一家
• 当 n >= 3时，我们要求的是从前n家中偷取可以获得的最大总价值

状态表示：f[i]：表示前i间房屋能偷取到的最大总金额为f[i]

针对第i家可以有两种以下情况偷或者不偷，要是偷第i家，那么第i-1家就不能偷了，这是题目规定的！

• 偷：f[i] = f[i - 2] + nums[i]
• 不偷：f[i] = f[i - 1]

状态计算：f[i] = max(f[i - 1], f[i - 2] + nums[i])(i >= 3)

初始化：

• f[0] = nums[0]
• f[1] = max(nums[0], nums[1])

Code

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

        int[]  f = new int[n + 10];
        f[0] = nums[0];
        f[1] = Math.max(nums[0], nums[1]);
        for(int i = 2; i < n; i ++){// 从第三家开始
            f[i] = Math.max(f[i - 1], f[i - 2] + nums[i]);
        }
        return f[n - 1];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

21. 打家劫舍 II

题目链接：213. 打家劫舍 II - 力扣（LeetCode）

思路：

这题和上一题的区别就是，本题是一个环，上一题是单链的形式，我们可以把环转化成链，然后用上一题的动态转移方程求解即可，转化为链可以分为以下三种情况：

• 情况一：不含首尾元素
• 情况二：含首元素不含尾元素
• 情况三：不含首元素含尾元素

这三种都是单链的形式，用打家劫舍I的方法求取本链的最大盗取金额即可，最终三者取最大即为答案！

Code

class Solution {

    public int rob(int[] nums) {
        int n = nums.length;
        if(nums == null || n == 0){
            return 0;
        }
        if(n == 1){
            return nums[0];
        }
        if(n == 2){// 这里要特判n = 2（不然下面没有情况1）
            return Math.max(nums[0], nums[1]);
        }

        int res1 = fun(nums, 1, n - 2);// 情况1（不含首尾）
        int res2 = fun(nums, 0, n - 2);// 情况2（含头不含尾）
        int res3 = fun(nums, 1, n - 1);// 情况3（含尾不含头）
        return Math.max(Math.max(res1, res2), res3);
    }

    // 打家劫舍I的处理方式
    public int fun(int[] nums, int l, int r){
        if(l == r) return nums[l];
        int[] f = new int[nums.length + 10];
        f[l] = nums[l];
        f[l + 1] = Math.max(nums[l], nums[l + 1]);
        for(int i = l + 2; i <= r; i ++){
            f[i] = Math.max(f[i - 1], f[i - 2] + nums[i]);
        }
        return f[r];
    }
}
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

上面的三种情况中，起始情况二和情况三已经包含了情况一，为此我们可以只考虑情况二和情况三即可：

class Solution {

    public int rob(int[] nums) {
        int n = nums.length;
        if(nums == null || n == 0){
            return 0;
        }
        if(n == 1){
            return nums[0];
        }

        int res2 = fun(nums, 0, n - 2);// 情况2（含头不含尾）
        int res3 = fun(nums, 1, n - 1);// 情况3（含尾不含头）
        return Math.max(res3, res2);
    }

    // 打家劫舍I的处理方式
    public int fun(int[] nums, int l, int r){
        if(l == r) return nums[l];
        int[] f = new int[nums.length + 10];
        f[l] = nums[l];
        f[l + 1] = Math.max(nums[l], nums[l + 1]);
        for(int i = l + 2; i <= r; i ++){
            f[i] = Math.max(f[i - 1], f[i - 2] + nums[i]);
        }
        return f[r];
    }
}
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

22. 打家劫舍 III（dfs+缓存/树形DP）

题目链接：337. 打家劫舍 III - 力扣（LeetCode）

Code

思路一：递归

依旧是打家劫舍I的思考方式，对于每一个根节点有偷和不偷两种情况：

• 偷根节点：那么它的左右儿子节点就不能偷了，那我们递归去偷它的左右子孙
• 不偷根节点：那么它的左右儿子节点就能偷了，那我们递归去偷它的左右儿子即可

最终两种情况取最值即可。

超时了！！

class Solution {
    public int rob(TreeNode root) {
        if(root == null){
            return 0;
        }
        return dfs(root);
    }
    public int dfs(TreeNode root){
        if(root == null){
            return 0;
        }

        // 偷根
        int res1 = root.val;
        if(root.left != null){
            res1 += (dfs(root.left.left) + dfs(root.left.right));
        }
        if(root.right != null){
            res1 += (dfs(root.right.left) + dfs(root.right.right));
        } 

        // 不偷根
        int res2 = 0;
        res2 += (dfs(root.left) + dfs(root.right));

        return Math.max(res1, res2);
    }
}
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

递归优化：之所以超时是存在了大量的重复计算，对于计算过的我们将其记录下来，当遇到时直接查表（空间换时间），我们可以用一个map来记录每一个根节点对于存/不存的情况，存的最大值即可（起始就是记忆化搜索）。

class Solution {
    Map<TreeNode, Integer> mp = new HashMap<>();
    public int rob(TreeNode root) {
        if(root == null){
            return 0;
        }
        return dfs(root);
    }
    public int dfs(TreeNode root){
        if(root == null){
            return 0;
        }
        // 遇到重复计算直接返回
        if(mp.containsKey(root)){
            return mp.get(root);
        }

        // 偷根
        int res1 = root.val;
        if(root.left != null){
            res1 += (dfs(root.left.left) + dfs(root.left.right));
        }
        if(root.right != null){
            res1 += (dfs(root.right.left) + dfs(root.right.right));
        } 
        // 不偷根
        int res2 = 0;
        res2 += (dfs(root.left) + dfs(root.right));

        // 记录最值
        int res = Math.max(res1, res2);
        mp.put(root, res);

        return res;
    }
}
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

思路二：动态规划（树形DP）

每一个节点是否选取，取决于它的左右子树是否选取。

假设f[0]：表示当前节点不选，f[1]：表示选取当前节点

fl[] fr[]分别表示左右子树节点是否选取（fl[1] fr[1]）和不选取（fl[0] fr[0]）的最大值。

那么状态转移方程：

• f[0]：f[0] = max(fl[0], fl[1]) + max(fr[0], fr[1])
• f[1]：f[1] = root.val + fl[0] + fr[0]

最终答案：max(f[0], f[1])，选根和不选根的最大情况

之所以采用有序遍历是因为，根节点的情况取决于左右子树的情况，为此先要递归计算出左右子树！

class Solution {
    public int rob(TreeNode root) {
        int[] f = new int[2];
        f = dfs(root);
        return Math.max(f[0], f[1]);
    }
    
    public int[] dfs(TreeNode root){
        if(root == null){
            return new int[]{0, 0};
        }
        
        // 分类讨论的标准是：当前结点偷或者不偷
        // 后续遍历
        // 由于需要后序遍历，所以先计算左右子结点，然后计算当前结点的状态值
        int[] fl = dfs(root.left);
        int[] fr = dfs(root.right);

        // 处理根
        int[] f = new int[2];
        f[0] = Math.max(fl[0], fl[1]) + Math.max(fr[0], fr[1]);// 偷根
        f[1] = root.val + fl[0] + fr[0];// 不偷根

        return f;
    }
}
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

23. 买卖股票的最佳时机

题目链接：121. 买卖股票的最佳时机 - 力扣（LeetCode）

Code

思路一：贪心

买入的时候股票的金额越小越好，固定左边的最小值，枚举右边若不断计算更新即可。

class Solution {
    int minPrice = 0x3f3f3f3f;
    public int maxProfit(int[] prices) {
        int res = 0; 
        for(int i = 0; i < prices.length; i ++){
            if(prices[i] < minPrice){
                minPrice = prices[i];
            }else if(prices[i] > minPrice){
                res = Math.max(res, prices[i] - minPrice);
            }
        }
        return res;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

思路二：动态规划

这题的思路跟打家劫舍的思路也很类型，我们也可以分为，到第i天结束时是否买入了股票（买入和没有买入）

定义二维数组：f[n][2]

状态表示：

f[i][0] 表示第i天没有持有股票所得最大现金（利润）

dp[i][1] 表示第i天持有股票所得最大现金（利润）

状态计算：

• f[i][0] = max(f[i - 1][0], f[i - 1][1] + prices[i]
• f[i][1] = max(f[i - 1][1], -prices[i])
  • 第i-1天就持有股票，那么就保持现状（不买入），所得现金就是昨天持有股票的所得现金 即：dp[i - 1][1]
  • 第i天买入股票（买入），所得现金就是买入今天的股票后所得现金即：-prices[i]

初始化：

• f[0][1] = -prices[0];
• f[0][0] = 0;

结果返回：f[n - 1][0]：最后一天不持有股票的最大利润（要么买了股票然后卖出去赚钱了，要么没买即为0）

class Solution {
    public int maxProfit(int[] prices) {
        int n = prices.length;
        int[][] f = new int[n][2];

        f[0][1] = -prices[0];
        f[0][0] = 0;
        for(int i = 1; i < n; i ++){
            f[i][0] = Math.max(f[i - 1][0], f[i - 1][1] + prices[i]);
            f[i][1] = Math.max(f[i - 1][1], -prices[i]);
        }
        return f[n - 1][0];
    }   
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14