【动态规划算法】之打家劫舍Ⅱ

发布时间:2023年12月24日

2.打家劫舍 II

在这里插入图片描述
和上一个比不同的就是,现在房屋围了一圈,第一个和最后一个相连

这道题目和198.打家劫舍 (opens new window)是差不多的,唯一区别就是成环了

对于一个数组,成环的话主要有如下三种情况:

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

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

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


注意我这里用的是"考虑",例如情况三,虽然是考虑包含尾元素,但不一定要选尾部元素! 对于情况三,取nums[1] 和 nums[3]就是最大的。

而情况二 和 情况三 都包含了情况一了,所以只考虑情况二和情况三就可以了。剩下的就和打家劫舍Ⅰ一样

代码如下

public static int rob(int[] nums) {
        if (nums.length == 0 || nums == null) {
            return 0;
        }
        if (nums.length == 1) {
            return nums[0];
        }
        int result1=fun(nums,0,nums.length-2);//情况二考虑首元素,不含尾元素
        int result2=fun(nums,1,nums.length-1);//情况三考虑尾元素,不含首元素
        return Math.max(result1,result2);

    }
    static int fun(int[] nums, int start, int end){
        //首尾相同 说明只有一个元素
        if (start==end){
            return nums[start];
        }
        int[] dp = new int[nums.length];
        dp[start] = nums[start];
        dp[start+1] = Math.max(nums[start], nums[start+1]);
        //因为成环了 所以首元素不是得从给定的satrt开始
        for (int i = start+2; i <= end; i++) {
            //如果偷第i个 那么应该是dp[i-2]+nums[i]
            //如果不偷第i个就可以考虑偷第i-1个 dp[i-1]
            dp[i] = Math.max(dp[i - 2] + nums[i], dp[i - 1]);
        }
        return dp[end];
    }
文章来源:https://blog.csdn.net/m0_48904153/article/details/135177143
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。