LeetCode(DP)House Robber

2018-06-16

House Robber

You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them is that adjacent houses have security system connected and it will automatically contact the police if two adjacent houses were broken into on the same night.

Given a list of non-negative integers representing the amount of money of each house, determine the maximum amount of money you can rob tonight without alerting the police.

Example 1:

Input: [1,2,3,1]
Output: 4
Explanation: Rob house 1 (money = 1) and then rob house 3 (money = 3).
             Total amount you can rob = 1 + 3 = 4.

Example 2:

Input: [2,7,9,3,1]
Output: 12
Explanation: Rob house 1 (money = 2), rob house 3 (money = 9) and rob house 5 (money = 1).
             Total amount you can rob = 2 + 9 + 1 = 12.

思路：一看题目就发现有很多种可能性，且计算量很大，这种问题一般都可以用动态规划来解决。难点在于如何找到这样的一个子问题来帮助我们解决这个大问题。由之前的“Maximum Subrrary”问题的启发。我们可以这样来看待这个问题，提出这样一个子问题：给定一个数组nums[i]表示的若干房子，小偷要偷盗的最后一个目标是nums[i]时他能偷到的最多钱是多少，这个结果用steal[i]表示。也就是说小偷必须要偷第nums[i]个房子，并且这是他偷的最后一个房子，之后的房子他不会再偷。我们可以发现，有这样的规律：

如果我们知道第i个房子的钱数目是nums[i]，这样我们在求steal[i]的时候可以这样求：

steal[i]=nums[i]+max{steal[i-2]，steal[i-4]，….steal[0] (或者是steal[1])};

从前往后就是：

steal[0]=nums[0];

steal[1]=nums[1];

steal[2]=nums[2]+max{steal[0]};

steal[3]=nums[3]+max{steal[1],steal[0]};

steal[4]=nums[4]+max{steal[2],steal[1],steal[0]};

…

steal[i]=nums[i]+max{steal[i-2]，steal[i-4]，….steal[0] (或者是steal[1]，取决于i的奇偶)};

由这个规律就可以求出每个子问题的解steal[i]，然后我们来看大问题：这个小偷如何偷盗才能在nums[i] (i=0~n-1)个房子中得到最多的钱，很明显小偷必须偷房子，而且他这个偷的行为也会有终点，因为不能被抓起来，否则就前功尽弃了。所以只要知道steal[i]中的最大值，就是小偷所有方案里边能偷到最多钱数的偷盗方案。

java代码如下：

class Solution {
    public int rob(int[] nums) {
        int len=nums.length;
        if(nums==null){
            return 0;
        }
        if(len==1){
            return nums[0];
        }
        if(len==2){
            return Math.max(nums[0],nums[1]);
        }
        //steal[i]表示以第i个房子作为最后一个偷盗的目标
        int max=0;
        int result=0;
        if(len>2){
            int [] steal=new int [len];
            steal[0]=nums[0];
            steal[1]=nums[1];
            max=nums[0];
            result=Math.max(steal[0],steal[1]);
        
            for(int i=2;i<len;i++){
                for(int j=i-2;j>=0;j--){
                    max=Math.max(max,steal[j]);
                }
                steal[i]=nums[i]+max;
                result=Math.max(result,steal[i]);
            }
        }
        
        return result;
    }
}