LeetCode——198. 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.

解题思路
从后向前考虑。以ex1为例（【1 2 3 1】）。
如果只有一个house，返回这个house的money。
如果有两个house，返回两个house的money的较大值。
如果有三个以上的house，sum_money只与当前house的money和i-2、i-3的sum_money有关。
因为i处的sum_money与1-1处的sum_money无关，所以最后要比较两个的大小。

代码实现：

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