打家劫舍系列(力扣198、213、337)Java动态规划

举报
玉面大蛟龙 发表于 2023/07/20 21:35:15 2023/07/20
【摘要】 一、打家劫舍(力扣198)        198. 打家劫舍-力扣        此题的动态规划有两种思路:        1、思路一:        可以参考前面相同题型的题解:https://bbs.huaweicloud.com/blogs/406132        房屋只有两种状态:被偷 和 没被偷        那么我们用dp数组来记录第i间房屋时的最大金额,dp[i][0] 记...

一、打家劫舍(力扣198)

        198. 打家劫舍-力扣

        此题的动态规划有两种思路:

        1、思路一:

        可以参考前面相同题型的题解:https://bbs.huaweicloud.com/blogs/406132

        房屋只有两种状态:被偷 和 没被偷

        那么我们用dp数组来记录第i间房屋时的最大金额,dp[i][0] 记录被偷的情况,dp[i][1]记录没被偷的情况。

        dp[i][0]表示被偷,那么前一间必然没有被偷,当前值就是前一间没有被偷的情况下的金额+当前金额,则dp[i][0] = dp[i-1][1] + nums[i]

        dp[i][1]表示没被偷,那么前一间可能被偷,也可能没被偷,当前值就是这两种情况中较大的那个,则dp[i][1] = max{ dp[i-1][0] , dp[i][1] }

        最后取dp[len-1][0]和dp[len-1][1]的较大值即可。考虑到当前房屋值只与前一间房屋有关,则可以用变量来代替dp数组,就成了下面的代码。

        在买卖股票的题解(上面的链接)中有此方法更详细的讲解和推导过程,感兴趣的朋友可以去看一下。

class Solution {
    public int rob(int[] nums) {
        int a = nums[0];
        int b = 0;
        for(int i=1; i<nums.length; i++) {
            int tempA = a;
            int tempB = b;
            a = tempB + nums[i];
            b = Math.max(tempA, tempB);
        }
        return Math.max(a, b);
    }
}


        2、思路二

        对于第k间房屋,只有两种情况:被偷 和 不被偷

        如果被偷,当前金额为k-2间房屋的金额+当前金额

        如果不被偷,当前金额为k-1间房屋金额

        这间房屋的金额就是两个值中较大的那个,所以得到递推公式:

                                                dp[i]=max(dp[i−2]+nums[i],dp[i−1])

class Solution {
 
    static int max = 0;
 
    public int rob(int[] nums) {
 
        if(nums.length==1){
            return nums[0];
        }
    
        int c = nums[0];
        int b = Math.max(nums[0], nums[1]);
        int a = nums[0];
        for(int i=2; i<nums.length; i++){
            a = Math.max(b, (c+nums[i]));
            c = b;
            b = a;
        }
        return Math.max(a, b);
    }
}

二、打家劫舍II(力扣213)

         这题与上题的不同在于,最后一家与第一家连在了一起,而我们动态规划出来的结果是无法知道第一家是否被偷的。那么,我们是不是可以分而治之,分为第一家被偷和第一家没被偷两种情况去看,这样问题就迎刃而解了。

        其中,偷东西的那部分代码可以抽取成方法,这样代码会更加简洁,但是分开写比较容易看清思路。 

class Solution {
    public int rob(int[] nums) {
        int res;
        int len = nums.length;
 
        if(len == 1) {
            return nums[0];
        }
        if(len == 2) {
            return Math.max(nums[0], nums[1]);
        }
 
        //第一间偷了
        int a;
        int b;
        if(len==3) {
            res = nums[0];
        } else {
            a = nums[2];
            b = 0;
            for(int i=3; i<len-1; i++) {
                int tempA = a;
                int tempB = b;
                a = tempB + nums[i];
                b = Math.max(tempA, tempB);
            }
            res = Math.max(a, b) + nums[0];
        }
 
        //第一间没偷
        a = nums[1];
        b = 0;
        for(int i=2; i<len; i++) {
            int tempA = a;
            int tempB = b;
            a = tempB + nums[i];
            b = Math.max(tempA, tempB);
        }
        res = Math.max(res, Math.max(a, b));
        return res;
    }
}

三、打家劫舍III(力扣337)

        337. 打家劫舍 III-力扣

        这次要偷的房子组成了一棵二叉树,我们简化一下题目:二叉树的节点上有权值,要求不能同时取父子节点的权值,问最大权值和是多少?

        首先,每个节点有两个状态:被偷 和 没被偷。我们使用a(i)来表示第i个节点被偷时,他和他的子树所贡献的最大权值;使用b(i)表示第i个节点不被偷时,他和他的子树所贡献的最大权值。那么:

        因为a(i)表示被偷,所以他的子节点不能被偷,那么他的权值和是左右子树不被偷时的权值和+当前节点权值,即:

                                                a(i) = b(i.left) + b(i.right) + i.val;

        因为b(i)表示当前节点不被偷,那么他的左右节点可以被偷也可以不被偷,我们取权值和较大的情况,即:

                            b(i) = max{a(i.left) , b(i.left)} + max{a(i.right) , b(i.right)}

        最终我们找出a(root) 和 b(root)中的较大值即可。a和b可考虑用哈希表来保存。

/**
 * 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 {
 
    Map<TreeNode, Integer> a;   //a.get(root) 表示当前节点被偷时,他和他的子树所能贡献的最大价值
    Map<TreeNode, Integer> b;   //b.get(root) 表示当前节点没被偷时,他和他的子树所能贡献的最大价值
 
    public int rob(TreeNode root) {
        a = new HashMap<>();
        b = new HashMap<>();
        dfs(root);
        return Math.max(a.get(root), b.get(root));
    }
 
    void dfs(TreeNode node) {
        if(node == null) {
            return;
        }
        dfs(node.left);
        dfs(node.right);
        a.put(node, b.getOrDefault(node.left, 0)+b.getOrDefault(node.right, 0)+node.val);
        b.put(node, 
        Math.max(a.getOrDefault(node.left, 0), b.getOrDefault(node.left, 0)) 
        + Math.max(a.getOrDefault(node.right, 0), b.getOrDefault(node.right, 0)));
    }
}

        不难看出,当前的ab值只与他的左右子树的ab值有关,所以,可以考虑将每次调用时的ab值返回给上一级调用,这样可以省去哈希表。

/**
 * 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 = dfs(root);
        return Math.max(res[0], res[1]);
    }
 
    int[] dfs(TreeNode node) {
        if(node == null) {
            return new int[]{0, 0};
        }
        int []left = dfs(node.left);
        int []right = dfs(node.right);
        //表示当前节点被偷时,他和他的子树所能贡献的最大价值
        int a = left[1] + right[1] + node.val;  
        //表示当前节点没被偷时,他和他的子树所能贡献的最大价值
        int b = Math.max(left[0], left[1]) + Math.max(right[0], right[1]);
        return new int[]{a, b};
    }
}


【版权声明】本文为华为云社区用户原创内容,转载时必须标注文章的来源(华为云社区)、文章链接、文章作者等基本信息, 否则作者和本社区有权追究责任。如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱: cloudbbs@huaweicloud.com
  • 点赞
  • 收藏
  • 关注作者

评论(0

0/1000
抱歉,系统识别当前为高风险访问,暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称,即可参与社区互动!

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。