leetcode 198.打家劫舍

leetcode 198.打家劫舍

题目描述

你是一个专业的小偷,计划偷窃沿街的房屋。每间房内都藏有一定的现金,影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统,如果两间相邻的房屋在同一晚上被小偷闯入,系统会自动报警。

给定一个代表每个房屋存放金额的非负整数数组,计算你 不触动警报装置的情况下 ,一夜之内能够偷窃到的最高金额。

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

示例 2:
输入:[2,7,9,3,1]
输出:12
解释:偷窃1号房屋 (金额 = 2), 偷窃3号房屋 (金额 = 9),接着偷窃5号房屋 (金额 =1)。
偷窃到的最高金额 = 2 + 9 + 1 = 12 。

提示:
0 <= nums.length <= 100
0 <= nums[i] <= 400

递归

简单来说,就是给你一个数组,然后将这个数组遍历一遍,并将数组中的值累加。
但是!这个累加是有条件限制的。
如果选择了数组下标i的值进行累加(偷窃),那么数组下标为i-1和数组下标为i+1的值就不能累加了(不能偷窃),即相邻的下标就不能累加了。

看上去好像只要将下标分成奇偶两类,然后分别累加一次,再比较两者的最大值就可以了,但这么做是不对的。

为什么会这样呢?站在小偷的视角看,一个房子(数组中的某个值)对他来说只有两个选择

  • 不偷

当他偷了某个房子(对下标为i的值进行了累加),那么下一个房子(下标为i+1的值)就不能再偷了,这点没问题。
但是,如果他没偷某个房子(对下标为i的值没有累加),那么对于下一个房子(下标为i+1的值)他其实会有两种选择:

  • 仍然选择不偷
  • 选择

小偷可能一开始偷的是奇数下标的房子,过了一段时间又开始偷偶数下标的房子,最后又开始偷奇数下标的房子。所以这种单纯判断奇偶下标的做法就不对了。

[1,2,3,1]这个数组为例,偷或者不偷的选择过程如下

对于递归函数来说,就需要传入两个参数:

  • 数组的下标,每次调用时下标都要+1
  • 状态,偷/不偷

对于状态来说有三种

  1. 如果传入的是偷,本次不偷
  2. 如果传入的是不,本次继续不偷
  3. 如果传入的是不,本次偷

递归执行的时间复杂是O(2^N)级别了,无法通过。
java代码:

class Solution {
    public int rob(int[] nums) {
        if(nums==null || nums.length==0) {
            return 0;
        }
        return dfs(nums,0,false);
    }
    //递归调用函数,index是选择数组的下标,status是状态
    //status=true表示上次是偷窃了,false表示上次不偷
    private int dfs(int[] nums,int index,boolean status) {
        if(index>=nums.length) {
            return 0;
        }
        int a=0,b=0,c=0;
        //状态不变,啥也不干
        a = dfs(nums,index+1,status);
        //上次偷了,本次不偷,啥也不干
        //上次不偷,本次偷窃
        if(status) {
            b = dfs(nums,index+1,false);
        }
        else {
            c = dfs(nums,index+1,true)+nums[index];
        }
        //求三种状态的结果的最大值
        return Math.max(Math.max(a,b),c);
    }
}
                                                                                    

python代码:

class Solution(object):
    def rob(self, nums):
        if not nums:
            return 0
        n = len(nums)
        # 递归调用函数,index是选择数组的下标,status是状态
        # status=1表示上次是偷窃了,0表示上次不偷
        def dfs(index,status):
            if index>=n:
                return 0
            a,b,c = 0,0,0
            # 状态不变,啥也不干
            a = dfs(index+1,status)
            # 上次偷了,本次不偷,啥也不干
            # 上次不偷,本次偷窃
            if status:
                b = dfs(index+1,0)
            else:
                c = dfs(index+1,1)+nums[index]
            # 求三种状态的结果的最大值    
            return max(a,b,c)
        return dfs(0,0)
                                                                                                                     

递归+记忆化

只要递归写出来了,记忆化只要加个缓存就可以了,去掉重复的调用。

java代码:

class Solution {
    public int rob(int[] nums) {
        if(nums==null || nums.length==0) {
            return 0;
        }
        //跟递归版本的一样,只是加了一个缓存而已
        int[][] cache = new int[nums.length][2];
        for(int i=0;i<cache.length;++i) {
            Arrays.fill(cache[i],-1);
        }
        return dfs(cache,nums,0,0);
    }
 
    private int dfs(int[][] cache,int[] nums,int index,int status) {
        if(index>=nums.length) {
            return 0;
        }
        if(cache[index][status]>-1) {
            return cache[index][status];
        }
        int a=0,b=0,c=0;
        a = dfs(cache,nums,index+1,status);
        if(status==1) {
            b = dfs(cache,nums,index+1,0);
        }
        else {
            c = dfs(cache,nums,index+1,1)+nums[index];
        }
        cache[index][status] = Math.max(Math.max(a,b),c);
        return cache[index][status];
    }
}
                                                                                                                                                 

python代码:

class Solution(object):
    def rob(self, nums):
        if not nums:
            return 0
        n = len(nums)
        # 跟递归版本的一样,只是加了一个缓存而已
        cache = dict()
        def dfs(index,status):
            if index>=n:
                return 0
            if (index,status) in cache:
                return cache[index,status]    
            a,b,c = 0,0,0
            a = dfs(index+1,status)
            if status:
                b = dfs(index+1,0)
            else:
                c = dfs(index+1,1)+nums[index]
            cache[index,status] = max(a,b,c)
            return cache[index,status]
        return dfs(0,0)
                                                                  

动态规划

我们先从小规模数组入手,看看他们的规律

1、如果数组只有两个元素,那么最大值就是max(nums[0],nums[1]),这个很简单。我们将这个结果记做x
2、如果数组有三个值呢,最大值就是max(nums[0]+nums[2],nums[1]),我们将这个结果记做y
3、数组有四个值的时候计算起来就不那么直观了,它是由max(x+nums[3],y)计算而来的,其中的x是第一步中计算结果;y是第二步的结算结果。如果将x和y展开就是

max(
    max(nums[0],nums[1])+nums[3],
    max(nums[0]+nums[2],nums[1])
)

我们将上述的计算结果记做z。
4、如果数组有5个值,其最终结果是max(y+nums[4],z),这里就不展开了。
通过观察上面几个数组,会发现有这么一些特点:

  • 当数组有4个值时,我们需要用到2个值的结果,以及3个值的结果。
  • 当数组有5个值时,我们需要用到3个值的结果,以及4个值的结果。
  • 那么当数组有6个值时,就需要用 到5个值的结果,以及4个值的结果。
  • 再进一步,当数组有k个值时,就需要用到k-1个值的结果,以及k-2个值的结果。

除了2个值和3个值之外,其他每次计算的时候,都需要用到前面的结果,那么我们就创建一个额外的dp数组,将每次计算的结果保存起来。
我们求nums[k]的最大值时,就需要用到dp[k-1]dp[k-2]

现在总结下这个累加后最大值的计算公式

最大值计算如下:

  • 由”nums[0],nums[1]..nums[end-2]”这段累加后的最大值,再将上nums[end]得来,对应的是上图中的x
  • 由”nums[0],nums[1]…nums[end-1]”这段累加后的最大值得来,对应上图中的y
  • 求max(x,y)即为最大值

所以动态规划的转移方程就是:

dp[i] = max(dp[i-1],dp[i-2]+nums[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[] dp = new int[nums.length];
        //如果只有一个元素那么最大值就是nums[0]
        //如果有两个元素最大值就是max(nums[0],nums[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-1],dp[i-2]+nums[i]);
        }
        //最大值就在数组的最后一位
        return dp[nums.length-1];
    }
}  
                                                                                

python代码:

class Solution(object):
    def rob(self, nums):
        if not nums:
            return 0
        n = len(nums)
        if n<2:
            return max(nums)
        dp = [0 for _ in xrange(n)]
        # 如果只有一个元素那么最大值就是nums[0]
        # 如果有两个元素最大值就是max(nums[0],nums[1])
        dp[0] = nums[0]
        dp[1] = max(nums[0],nums[1])
        # 利用前面两个位置的最大值计算本次的最大值
        for i in xrange(2,n):
            dp[i] = max(dp[i-1],dp[i-2]+nums[i])
        # 最大值就在数组的最后一位
        return dp[-1]
                                                                        

动态规划+空间优化

动态规划中,我们计算nums[k] 的值时,需要用到dp[k-2]dp[k-1]的值。
而计算nums[k+1]时,需要用到dp[k]dp[k-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 pre = 0;
        int cur = 0;
        //每次计算nums[i]时,需要用到dp[i-2]和dp[i-1]
        //这里用pre代替dp[i-2],cur代替dp[i-1],省掉一维数组空间
        for(int i=0;i<nums.length;++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
        pre = 0
        cur = 0
        # 每次计算nums[i]时,需要用到dp[i-2]和dp[i-1]
        # 这里用pre代替dp[i-2],cur代替dp[i-1],省掉一维数组空间
        for i in nums:
            cur,pre = max(cur,pre+i),cur
        return cur
                                                                       

 

 

1 次阅读

发表评论

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