代码随想录算法训练营第四十八天|198.打家劫舍、213.打家劫舍II、337.打家劫舍III

2024-01-02 12:33:42

代码随想录 (programmercarl.com)

198.打家劫舍

1.确定dp数组以及下标的含义

dp[i]:考虑下标i(包括i)以内的房屋,最多可以偷窃的金额为dp[i]

2.确定递推公式

决定dp[i]的因素就是第i房间偷还是不偷。

如果偷第i房间,那么dp[i] = dp[i - 2] + nums[i] ,即:第i-1房一定是不考虑的,找出 下标i-2(包括i-2)以内的房屋,最多可以偷窃的金额为dp[i-2] 加上第i房间偷到的钱。

如果不偷第i房间,那么dp[i] = dp[i - 1],即考虑i-1房,(注意这里是考虑,并不是一定要偷i-1房

然后dp[i]取最大值,即dp[i] = max(dp[i - 2] + nums[i], dp[i - 1]);

3.dp数组初始化

dp[0] 一定是 nums[0],dp[1]就是nums[0]和nums[1]的最大值即:dp[1] = max(nums[0], nums[1]);

4.遍历顺序

dp[i] 是根据dp[i - 2] 和 dp[i - 1] 推导出来的,那么一定是从前到后遍历

class Solution {
    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 + 1];
        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 - 2] + nums[i], dp[i - 1]);
        }
        return dp[nums.length - 1];
    }
}

需要提前将其他特殊情况考虑到,比如数组长度为0或1的情况。

213.打家劫舍II

一个数组成环之后,需要考虑三种情况:

情况一:考虑不包含首尾元素

情况二:考虑不包含尾元素

情况三:考虑不包含首元素

此处注意是【考虑】,不是一定要“偷”,情况二和情况三是包含情况一的,所以只需要考虑情况二和情况三即可。

class Solution {
    public int rob(int[] nums) {
        int len = nums.length;
        if (nums == null | len == 0){
            return 0;
        }
        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 pre = 0, cur = 0, tmp;
        for(int i = start; i < end; i++){
            tmp = cur;
            cur = Math.max(pre + nums[i], cur);
            pre = tmp;
        }
        return cur;
    }
}

注意:代码中pre的取值是关键,确保不会“偷”到相邻的房屋!

337.打家劫舍III

树形dp问题入门===递归三部曲+动规五部曲

1.确定递归函数的参数和返回值

确定dp数组以及下标的含义

偷dp[0]与不偷dp[1]这个节点

dp[i]:下标为0记录不偷该节点所得到的的最大金钱,下标为1记录偷该节点所得到的的最大金钱。

所以本题dp数组就是一个长度为2的数组

2.确定终止条件

在遍历的过程中,如果遇到空节点的话,无论偷还是不偷都是0,所以就返回。

相当于dp数组的初始化。

3.遍历顺序

后序遍历(左右中),?因为要通过递归函数的返回值来做下一步计算。

4.确定单层递归的逻辑(中)

如果是偷当前节点,那么左右孩子就不能偷,val1 = cur->val + left[0] + right[0];?

如果不偷当前节点,那么左右孩子就可以偷,至于到底偷不偷一定是选一个最大的,所以:val2 = max(left[0], left[1]) + max(right[0], right[1]);

最后当前节点的状态就是{val2, val1}; 即:{不偷当前节点得到的最大金钱,偷当前节点得到的最大金钱}

dp[0],dp[1]对应于va2,val1,前者不偷,后者偷。

/**
 * Definition for a binary tree node.
 * public 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) {
        int[] res = robAction(root);
        return Math.max(res[0], res[1]);
    }
    int[] robAction(TreeNode root){
        int[] res = new int[2];
        if (root == null){//递归终止条件
            return res;//返回初始化的[0,0]
        }
        //后序遍历:左-右-中
        int[] left = robAction(root.left);//左
        int[] right = robAction(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;
    }
}

文章来源:https://blog.csdn.net/YOYU_/article/details/135294492
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。