House Robber 392

Question

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

Given [3, 8, 4], return 8.

Challenge

O(n) time and O(1) memory.

Solution

val[i]表示抢第i幢房子时能取得的最大值。有两种情况，即抢第i幢房子，则其最大值为val[i-2]+A[i-1]，或者不抢第i幢房子，则其最大值为val[i-1]，比较两者取大的即可。

状态函数：val[i]=max(val[i-1], val[i-2]+A[i-1])

但是题目要求用O(1)的space，所以需要用滚动数组优化，因为对于每个i，只和i－1以及i－2相关，因此用长度为2的数组即可，满足题意。

代码如下：

public class Solution {
    /**
     * @param A: An array of non-negative integers.
     * return: The maximum amount of money you can rob tonight
     */
    public long houseRobber(int[] A) {
        // write your code here
        if(A == null || A.length == 0){
            return 0;
        }

        int n = A.length;
        long[] val = new long[2];
        val[0] = 0;
        val[1] = A[0];

        for(int i = 2; i <= n; i++){
            val[i % 2] = Math.max(val[(i - 1) % 2], val[(i - 2) % 2] + A[i - 1]);
        }

        return val[n % 2];
    }
}