HourseRobber [source code]

public class HourseRobber {
static
/******************************************************************************/
public class Solution {
    public int rob(int[] nums) {
        if (nums.length == 0) return 0;
        if (nums.length == 1) return nums[0];
        int[] memo = new int[Math.max(nums.length + 1, 3)];
        memo[0] = 0;
        memo[1] = nums[0];
        for (int i = 2; i < memo.length ; i++) {
            memo[i] = Math.max(nums[i - 1] + memo[i - 2], memo[i - 1]);
        }
        return memo[nums.length];
    }
}
/******************************************************************************/

    public static void main(String[] args) {
        HourseRobber.Solution tester = new HourseRobber.Solution();
    }
}

这个题目总体来说也是 DP 的一个经典题型了, 本身还是很简单的, 就是有两个难点:

• Corner Case 的处理;
• memo 和 nums 的两个 index 之间的变换;

首先我们做 memo, memo 的长度使用一个 max 来表示至少要有3, 这个以前是见过的了. 而且要用nums.length + 1来做长度, 这个也是 DP 问题的常规了;

一开始碰到一个问题就是 memo[1]到底 init 到什么?

memo[1] = 1;  
memo[1] = nums[1];  
memo[1] = nums[0];

第一个肯定不对, 不能想当然的就认为是1, 哪来的1; 第二个看起来对, 其实也不对; 只有第三个是对的;

这个就涉及到一个nums 和 memo 之间的 index 变换的问题; 我们可以认为 nums 里面每一个 entry代表一个房子: nums[0]代表房子0; 这里的0你可以看成是一个名字, 实际上房子0是第一所房子;
而你的 memo 里面代表的是什么呢? 你 memo[0]能不能也代表当 nums ends at house0的时候的 memo 呢? 显然是不能的, 因为 memo 的[0]向来是有特殊用途的.
所以我们只能说memo[1]代表 nums[0];那么这两个 index 之间就存在了一个-1的关系; 这个关系看起来很小, 但是写代码的时候还是挺容易出错的, 比如这里的这个 init, 还有比如循环里面的

memo[i] = Math.max(nums[i - 1] + memo[i - 2], memo[i - 1]);

看起来就很不自然, 因为按理应该是memo[i - 2] + nums[i]的感觉(选择了 i, 就不选择i-1).

最后的速度是0(40), 应该是没什么问题的;

当然这个算法空间上是可以优化到O(1)的, but again, fear premature optimization;

这个是 discussion 上面看到的一个有意思的写法:

int rob(int num[], int n) {  
    int a = 0;  
    int b = 0;  

    for (int i=0; i<n; i++)  
    {  
        if (i%2==0)  
        {  
            a = max(a+num[i], b);  
        }  
        else  
        {  
            b = max(a, b+num[i]);  
        }  
    }  

    return max(a, b);  
}

这个是解释:

it is similar to dp, you could consider a as previous max num at even, b as previous max num at odd.

这个是一个强行给 memo 加了一维的写法:

public int rob(int[] num) {  
    int[][] dp = new int[num.length + 1][2];  
    for (int i = 1; i <= num.length; i++) {  
        dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1]);  
        dp[i][1] = num[i - 1] + dp[i - 1][0];  
    }  
    return Math.max(dp[num.length][0], dp[num.length][1]);  
}

dp[i][1] means we rob the current house and dp[i][0] means we don't,

总体思路还是类似的;

Problem Description

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.

Credits:
Special thanks to @ifanchu for adding this problem and creating all test cases. Also thanks to @ts for adding additional test cases.

Difficulty:Easy
Category:Algorithms
Acceptance:38.59%
Contributor: LeetCode
Companies
linkedin airbnb
Related Topics
dynamic programming
Similar Questions
Maximum Product Subarray House Robber II Paint House Paint Fence House Robber III Non-negative Integers without Consecutive Ones