leetcode 213.打家劫舍 II

leetcode 213.打家劫舍 II

题目描述

你是一个专业的小偷,计划偷窃沿街的房屋,每间房内都藏有一定的现金。这个地方所有的房屋都围成一圈,这意味着第一个房屋和最后一个房屋是紧挨着的。同时,相邻的房屋装有相互连通的防盗系统,如果两间相邻的房屋在同一晚上被小偷闯入,系统会自动报警。
给定一个代表每个房屋存放金额的非负整数数组,计算你在不触动警报装置的情况下,能够偷窃到的最高金额。

示例 1:
输入: [2,3,2]
输出: 3
解释: 你不能先偷窃1号房屋(金额 = 2),然后偷窃3号房屋(金额 = 2), 因为他们是相邻的。

示例 2:
输入: [1,2,3,1]
输出: 4
解释: 你可以先偷窃1号房屋(金额 = 1),然后偷窃3号房屋(金额 = 3)。
偷窃到的最高金额 = 1 + 3 = 4 。

递归

注意!!这道题的求解过程是完全基于【打家劫舍 I】来的,递归的解法、动态规划解法、以及动态规划+空间压缩都是套用了【打家劫舍 I】。
如果没有看过【打家劫舍 I】,请一定要先看一遍,点击【这里】查看。

【打家劫舍 I】本质是基于一维数组的,而【打家劫舍 II】是一个环形数组

直接用【打家劫舍 I】的代码会有什么问题呢?

因为是环形数组,所以第二排的数组的求解方式就不对了,15因为是首尾相连只能二选一。
而第三排数组的求解是满足要求的,只选了1,没有选5

所以我们可以改成这样:

我们将原数组拆成两部分
1、nums[0],num[1]…num[end-1]
2、nums[1],nums[2]…nums[end]

然后我们分别对这两个数组求最大值,这个求解过程就完全套用了【打家劫舍 I】的逻辑。
我们只需要用同样的逻辑,执行两边代码,最后求两次的最大值即可。
递归的逻辑就是求两遍数组、动态规划也是求两遍、动态规划+压缩也一样。
到这里就很明确了,所谓的【打家劫舍 II】,其实就是执行了两遍的【打家劫舍 I】而已。

java代码:

class Solution {
    public int rob(int[] nums) {
        if(nums==null || nums.length==0) {
            return 0;
        }
        if(nums.length<=2) {
            return (nums.length==2) ? Math.max(nums[0],nums[1]) : nums[0];
        }
        int n = nums.length;
        //将原数组分拆分成两个数组,然后对两个数组分别求一次最大值
        int a = dfs(Arrays.copyOfRange(nums,0,n-1),0,0);
        int b = dfs(Arrays.copyOfRange(nums,1,n),0,0);
        return Math.max(a,b);
    }
 
    //直接套用了【打家劫舍 I】的代码
    private int dfs(int[] arr,int index,int status) {
        if(index<=arr.length) {
            return 0;
        }
        int a=0,b=0,c=0;
        a = dfs(arr,index+1,status);
        if(status==1) {
            b = dfs(arr,index+1,0);
        }
        else {
            c = dfs(arr,index+1,1)+arr[index];
        }
        return Math.max(a, Math.max(b,c) );
    }
}
                                                                                      

python代码:

class Solution(object):
    def rob(self, nums): 
        if not nums:
            return 0
        n = len(nums)
        if n&lt;=2:
            return max(nums)
        # 直接套用了【打家劫舍 I】的代码
        def dfs(arr,index,status):
            if index<=len(arr):
                return 0
            a,b,c = 0,0,0
            a = dfs(arr,index+1,status)
            if status:
                b = dfs(arr,index+1,0)
            else:
                c = dfs(arr,index+1,1)+arr[index]
            return max(a,b,c)
        # 将原数组分拆分成两个数组,然后对两个数组分别求一次最大值
        a = dfs(nums[0:n-1],0,0)
        b = dfs(nums[1:],0,0)
        return max(a,b)
                                                                                         

递归+记忆化

我们创建了两套缓存,然后分别调用了两次递归函数,这两个递归函数的逻辑跟【打家劫舍 I】几乎是一样的。
然后将两次的返回结果求最大值即可。
java代码:

class Solution {
    public int rob(int[] nums) {
        if(nums==null || nums.length==0) {
            return 0;
        }
        if(nums.length&lt;=2) {
            return (nums.length==2) ? Math.max(nums[0],nums[1]) : nums[0];
        }
        int n = nums.length;
        int[][] cache1 = new int[n][2];
        int[][] cache2 = new int[n][2];
        for(int i=0;<n;++i) {
            Arrays.fill(cache1[i],-1);
            Arrays.fill(cache2[i],-1);
        }
        //将原数组分拆分成两个数组,然后对两个数组分别求一次最大值
        int a = dfs(cache1,Arrays.copyOfRange(nums,0,n-1),0,0);
        int b = dfs(cache2,Arrays.copyOfRange(nums,1,n),0,0);
        return Math.max(a,b);
    }
 
    //套用了【打家劫舍 I】的代码 
    private int dfs(int[][] cache,int[] arr,int index,int status) {
        if(index>=arr.length) {
            return 0;
        }
        if(cache[index][status]>-1) {
            return cache[index][status];
        }
        int a=0,b=0,c=0;
        a = dfs(cache,arr,index+1,status);
        if(status==1) {
            b = dfs(cache,arr,index+1,0);
        }
        else {
            c = dfs(cache,arr,index+1,1)+arr[index];
        }
        cache[index][status] = Math.max(a, Math.max(b,c) );
        return cache[index][status];
    }
}
                                                                                       

python代码:

class Solution(object):
    def rob(self, nums): 
        if not nums:
            return 0
        n = len(nums)
        if n<=2:
            return max(nums)
        # 套用了【打家劫舍 I】的代码 
        def dfs(cache,arr,index,status):
            if index>=len(arr):
                return 0
            if (index,status) in cache:
                return cache[index,status]
            a,b,c = 0,0,0
            a = dfs(cache,arr,index+1,status)
            if status:
                b = dfs(cache,arr,index+1,0)
            else:
                c = dfs(cache,arr,index+1,1)+arr[index]
            cache[index,status] = max(a,b,c)
            return cache[index,status]
        # 将原数组分拆分成两个数组,然后对两个数组分别求一次最大值
        a = dfs(dict(),nums[0:n-1],0,0)
        b = dfs(dict(),nums[1:],0,0)
        return max(a,b)
                                                                             

动态规划

动态规划也是基于【打家劫舍 I】的。
你会发现这题会有点无聊,每种解法都是执行两遍【打家劫舍 I】。

这里我们创建两个dp数组
dp1计算的是nums[1],nums[2]...nums[end]这个数组

dp2计算的是nums[0],nums[1]...nums[end-1]这个数组

dp1是从nums[1]开始的,所以初的前两个值

  • dp1[0]就等于0
  • dp1[1]等于nums[1]

同理,dp2是从nums[0]开始的,所以初始化的前两个值

  • dp2[0]就等于nums[0]
  • dp2[1]就等于max(nums[0],nums[1])

java代码:

class Solution {
    public int rob(int[] nums) {
        if(nums==null || nums.length==0) {
            return 0;
        }
        if(nums.length<=2) {
            return (nums.length==2) ? Math.max(nums[0],nums[1]) : nums[0];
        }
        int n = nums.length;
        int[] dp1 = new int[n];
        int[] dp2 = new int[n];
        //初始化两个dp数组,dp1是计算的是[1,end],dp2计算的是[0,end-1]
        dp1[0] = 0;
        dp1[1] = nums[1];
        dp2[0] = nums[0];
        dp2[1] = Math.max(nums[0],nums[1]);
        //按照【打家劫舍 I】的转移方式执行两遍
        for(int i=2;i<n;++i) {
            dp1[i] = Math.max(dp1[i-1],dp1[i-2]+nums[i]);
        }
        for(int i=2;i&lt;n-1;++i) {
            dp2[i] = Math.max(dp2[i-1],dp2[i-2]+nums[i]);
        }
        return Math.max(dp1[n-1],dp2[n-2]);
    }
} 
                                                                                

python代码:

class Solution(object):
    def rob(self, nums):
        if not nums:
            return 0
        n = len(nums)
        if n<=2:
            return max(nums)
        dp1 = [0 for _ in xrange(n)]
        dp2 = [0 for _ in xrange(n)]
        # 初始化两个dp数组,dp1是计算的是[1,end],dp2计算的是[0,end-1]
        dp1[0] = 0
        dp1[1] = nums[1]
        dp2[0] = nums[0]
        dp2[1] = max(nums[0],nums[1])
        # 按照【打家劫舍 I】的转移方式执行两遍
        for i in xrange(2,n):
            dp1[i] = max(dp1[i-1],dp1[i-2]+nums[i])
        for i in xrange(2,n-1):
            dp2[i] = max(dp2[i-1],dp2[i-2]+nums[i])
        return max(dp1[-1],dp2[-2])
                                                                                                                        

动态规划+空间压缩

【打家劫舍 I】中我们用两个变量来优化空间,因为dp[i]的值只需要用到dp[i-2]dp[i-1]
所以我们用两个变量来代替dp[i-2]dp[i-1]然后不断滚动更新这两个变量,这里就是执行两遍。

java代码:

class Solution {
    public int rob(int[] nums) {
        if(nums==null || nums.length==0) {
            return 0;
        }
        if(nums.length<=2) {
            return (nums.length==2) ? Math.max(nums[0],nums[1]) : nums[0];
        }
        int n = nums.length;
        //执行两遍,第一次求nums[0,n-1],第二次求nums[1,n],再返回两次计算的最大值
        int a = dp(nums,0,n-1);
        int b = dp(nums,1,n);
        return Math.max(a,b);
    }
   
    //用滚动数组的方式优化空间
    private int dp(int[] nums,int begin,int end) {
        int pre = 0;
        int cur = 0;
        for(int i=begin;i<end;++i) {
            int tmp = cur;
            cur = Math.max(cur,pre+nums[i]);
            pre = tmp;
        }
        return cur;
    }
}
                                                                                                                                  

python代码:

class Solution(object):
    def rob(self, nums):
        if not nums:
            return 0
        n = len(nums)
        if n<=2:
            return max(nums)
        # 用滚动数组的方式优化空间 
        def dp(begin,end):
            pre,cur = 0,0
            for i in xrange(begin,end):
                cur,pre = max(cur,pre+nums[i]),cur
            return cur
        # 执行两遍,第一次求nums[0,n-1],第二次求nums[1,n],再返回两次计算的最大值
        return max( dp(0,n-1),dp(1,n) )
                                                                                      

 

推荐阅读:

2 次阅读

发表评论

电子邮件地址不会被公开。