198. 打家劫舍

输入: [1,2,3,1]
输出: 4
解释: 偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。
     偷窃到的最高金额 = 1 + 3 = 4 。

输入: [2,7,9,3,1]
输出: 12
解释: 偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9)，接着偷窃 5 号房屋 (金额 = 1)。
     偷窃到的最高金额 = 2 + 9 + 1 = 12 。

class Solution {
    public int rob(int[] nums) {
        int len = nums.length;
        if (len == 0) {
            return 0;
        }
        if (len == 1) {
            return nums[0];
        }
        //dp[i]表示nums从0~（i-1）
        int[] dp = new int[len + 1];
        //初始化
        dp[1] = nums[0];
        dp[2] = Math.max(nums[0], nums[1]);
        //状态转移
        for (int i = 3; i <= len; i++) {
            dp[i] = Math.max((nums[i - 1] + dp[i - 2]), dp[i - 1]);
        }
        return dp[len];
    }
}