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.

一道动态规划的问题，题目的本质就是给定一个数组，从中选出一个最大的和，要求每相邻的两个元素不可以同时选择。我们构造一个dp数组，dp[i]代表到当前元素能组成的最大的和，每当我们访问一个新的元素，我们要判断当前元素与dp[i - 2]的和与dp[i]的大小，也就是dp[i] = Math.max(nums[i - 1] + dp[i - 2], dp[i - 1])（i > 1); 这就是动态转移方程。具体代码如下:

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