代码随想录-算法训练营day47【动态规划09：打家劫舍、打家劫舍II、打家劫舍III】

2024 年 7 月 21 日 16点热度 0人点赞 0条评论

代码随想录-035期-算法训练营【博客笔记汇总表】-CSDN博客

第九章 动态规划part09

● 198.打家劫舍 
● 213.打家劫舍II  
● 337.打家劫舍III

 详细布置 

今天就是打家劫舍的一天，这个系列不算难，大家可以一口气拿下。

 198.打家劫舍  
视频讲解：https://www.bilibili.com/video/BV1Te411N7SX
https://programmercarl.com/0198.%E6%89%93%E5%AE%B6%E5%8A%AB%E8%88%8D.html  

 213.打家劫舍II  
视频讲解：https://www.bilibili.com/video/BV1oM411B7xq
https://programmercarl.com/0213.%E6%89%93%E5%AE%B6%E5%8A%AB%E8%88%8DII.html 

 337.打家劫舍III  
视频讲解：https://www.bilibili.com/video/BV1H24y1Q7sY
https://programmercarl.com/0337.%E6%89%93%E5%AE%B6%E5%8A%AB%E8%88%8DIII.html

往日任务
● day 1 任务以及具体安排：https://docs.qq.com/doc/DUG9UR2ZUc3BjRUdY  
● day 2 任务以及具体安排：https://docs.qq.com/doc/DUGRwWXNOVEpyaVpG  
● day 3 任务以及具体安排：https://docs.qq.com/doc/DUGdqYWNYeGhlaVR6 
● day 4 任务以及具体安排：https://docs.qq.com/doc/DUFNjYUxYRHRVWklp 
● day 5 周日休息
● day 6 任务以及具体安排：https://docs.qq.com/doc/DUEtFSGdreWRuR2p4 
● day 7 任务以及具体安排：https://docs.qq.com/doc/DUElCb1NyTVpXa0Jj 
● day 8 任务以及具体安排：https://docs.qq.com/doc/DUGdsY2JFaFhDRVZH 
● day 9 任务以及具体安排：https://docs.qq.com/doc/DUHVXSnZNaXpVUHN4 
● day 10 任务以及具体安排：https://docs.qq.com/doc/DUElqeHh3cndDbW1Q 
●day 11 任务以及具体安排：https://docs.qq.com/doc/DUHh6UE5hUUZOZUd0 
●day 12 周日休息 
●day 13 任务以及具体安排：https://docs.qq.com/doc/DUHNpa3F4b2dMUWJ3 
●day 14 任务以及具体安排：https://docs.qq.com/doc/DUHRtdXZZSWFkeGdE 
●day 15 任务以及具体安排：https://docs.qq.com/doc/DUHN0ZVJuRmVYeWNv 
●day 16 任务以及具体安排：https://docs.qq.com/doc/DUHBQRm1aSWR4T2NK 
●day 17 任务以及具体安排：https://docs.qq.com/doc/DUFpXY3hBZkpabWFY 
●day 18 任务以及具体安排：https://docs.qq.com/doc/DUFFiVHl3YVlReVlr 
●day 19 周日休息
●day 20 任务以及具体安排：https://docs.qq.com/doc/DUGFRU2V6Z1F4alBH  
●day 21 任务以及具体安排：https://docs.qq.com/doc/DUHl2SGNvZmxqZm1X 
●day 22 任务以及具体安排：https://docs.qq.com/doc/DUHplVUp5YnN1bnBL  
●day 23 任务以及具体安排：https://docs.qq.com/doc/DUFBUQmxpQU1pa29C 
●day 24 任务以及具体安排：https://docs.qq.com/doc/DUEhsb0pUUm1WT2NP  
●day 25 任务以及具体安排：https://docs.qq.com/doc/DUExTYXVzU1BiU2Zl 
●day 26 休息 
●day 27 任务以及具体安排：https://docs.qq.com/doc/DUElpbnNUR3hIbXlY 
●day 28 任务以及具体安排：https://docs.qq.com/doc/DUG1yVHdlWEdNYlhZ  
●day 29 任务以及具体安排：https://docs.qq.com/doc/DUHZYbWhwSHRCRmp3 
●day 30 任务以及具体安排：https://docs.qq.com/doc/DUEdTVVhxbnJiY3BR 
●day 31 任务以及具体安排：https://docs.qq.com/doc/DUG1PQ1ZZY2xXY1ly 
●day 32 任务以及具体安排：https://docs.qq.com/doc/DUGFEdGFWeVhleFF1 
●day 33 周日休息 
●day 34 任务以及具体安排：https://docs.qq.com/doc/DUEh5WFVlQkp1U0p4  
●day 35 任务以及具体安排：https://docs.qq.com/doc/DUFRWc3BGRHFXZ1pO  
●day 36 任务以及具体安排：https://docs.qq.com/doc/DUERGbnhhRkFRVENZ 
●day 37 任务以及具体安排：https://docs.qq.com/doc/DUFVRd3p5SHFMSExQ  
●day 38 任务以及具体安排：https://docs.qq.com/doc/DUGNUdVpoT0VJR01l 
●day 39 任务以及具体安排：https://docs.qq.com/doc/DUE55cVJ5WkNoREhS 
●day 40 周日休息
●day 41 任务以及具体安排：https://docs.qq.com/doc/DUFhIUXRFYnVGUkFp 
●day 42 任务以及具体安排：42 第八章 动态规划 
●day 43 任务以及具体安排：43第八章 动态规划 
●day 44 任务以及具体安排：44 第八章 动态规划 
●day 45 任务以及具体安排：45  第八章 动态规划 
●day 46 任务以及具体安排：46 第八章 动态规划 
●day 47 周日休息

0198_打家劫舍

0213_打家劫舍II

0337_打家劫舍III

0198_打家劫舍

package com.question.solve.leetcode.programmerCarl2._10_dynamicProgramming;

public class _0198_打家劫舍 {
}

//动态规划
class Solution0198 {
    public int rob(int[] nums) {
        if (nums == null || nums.length == 0) return 0;
        if (nums.length == 1) return nums[0];

        int[] dp = new int[nums.length];
        dp[0] = nums[0];
        dp[1] = Math.max(dp[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];
    }
}

//使用滚动数组思想，优化空间
//分析本题可以发现，所求结果仅依赖于前两种状态，此时可以使用滚动数组思想将空间复杂度降低为3个空间
class Solution0198_2 {
    public int rob(int[] nums) {
        int len = nums.length;
        if (len == 0) return 0;
        else if (len == 1) return nums[0];
        else if (len == 2) return Math.max(nums[0], nums[1]);

        int[] result = new int[3];//存放选择的结果
        result[0] = nums[0];
        result[1] = Math.max(nums[0], nums[1]);

        for (int i = 2; i < len; i++) {
            result[2] = Math.max(result[0] + nums[i], result[1]);
            result[0] = result[1];
            result[1] = result[2];
        }
        return result[2];
    }
}

//进一步对滚动数组的空间优化 dp数组只存与计算相关的两次数据
class Solution0198_3 {
    public int rob(int[] nums) {
        if (nums.length == 1) {
            return nums[0];
        }
        //初始化dp数组
        //优化空间，dp数组只用2格空间，只记录与当前计算相关的前两个结果
        int[] dp = new int[2];
        dp[0] = nums[0];
        dp[1] = Math.max(nums[0], nums[1]);
        int res = 0;
        //遍历
        for (int i = 2; i < nums.length; i++) {
            res = Math.max((dp[0] + nums[i]), dp[1]);
            dp[0] = dp[1];
            dp[1] = res;
        }
        //输出结果
        return dp[1];
    }
}

0213_打家劫舍II

package com.question.solve.leetcode.programmerCarl2._10_dynamicProgramming;

public class _0213_打家劫舍II {
}

class Solution0213 {
    public int rob(int[] nums) {
        if (nums == null || nums.length == 0)
            return 0;
        int len = nums.length;
        if (len == 1)
            return nums[0];
        return Math.max(robAction(nums, 0, len - 1), robAction(nums, 1, len));
    }

    int robAction(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(y, x + nums[i]);
            x = y;
        }
        return z;
    }
}

0337_打家劫舍III

package com.question.solve.leetcode.programmerCarl2._10_dynamicProgramming;

import java.util.HashMap;
import java.util.Map;

public class _0337_打家劫舍III {
}

class Solution0337 {
    //1.递归去偷，超时
    public int rob(TreeNode root) {
        if (root == null)
            return 0;
        int money = root.val;
        if (root.left != null) {
            money += rob(root.left.left) + rob(root.left.right);
        }
        if (root.right != null) {
            money += rob(root.right.left) + rob(root.right.right);
        }
        return Math.max(money, rob(root.left) + rob(root.right));
    }

    //2.递归去偷，记录状态
    //执行用时：3 ms , 在所有 Java 提交中击败了 56.24% 的用户
    public int rob2(TreeNode root) {
        Map<TreeNode, Integer> memo = new HashMap<>();
        return robAction(root, memo);
    }

    int robAction(TreeNode root, Map<TreeNode, Integer> memo) {
        if (root == null)
            return 0;
        if (memo.containsKey(root))
            return memo.get(root);
        int money = root.val;
        if (root.left != null) {
            money += robAction(root.left.left, memo) + robAction(root.left.right, memo);
        }
        if (root.right != null) {
            money += robAction(root.right.left, memo) + robAction(root.right.right, memo);
        }
        int res = Math.max(money, robAction(root.left, memo) + robAction(root.right, memo));
        memo.put(root, res);
        return res;
    }

    //3.状态标记递归
    //执行用时：0 ms , 在所有 Java 提交中击败了 100% 的用户
    //不偷：Max(左孩子不偷，左孩子偷) + Max(右孩子不偷，右孩子偷)
    //root[0] = Math.max(rob(root.left)[0], rob(root.left)[1]) +
    //Math.max(rob(root.right)[0], rob(root.right)[1])
    //偷：左孩子不偷+ 右孩子不偷 + 当前节点偷
    //root[1] = rob(root.left)[0] + rob(root.right)[0] + root.val;
    public int rob3(TreeNode root) {
        int[] res = robAction1(root);
        return Math.max(res[0], res[1]);
    }

    int[] robAction1(TreeNode root) {
        int res[] = new int[2];
        if (root == null)
            return res;

        int[] left = robAction1(root.left);
        int[] right = robAction1(root.right);

        res[0] = Math.max(left[0], left[1]) + Math.max(right[0], right[1]);
        res[1] = root.val + left[0] + right[0];
        return res;
    }
}

本作品采用知识共享署名 4.0 国际许可协议进行许可