version at: 2022-04-21

/**
1. 状态转移独立且只和之前的状态相关
2, 状态定义, f[i] 到第i个房子时, 抢到金额的最大值
3. 状态计算: f[i] 有2种可能 当前不抢: f[i-1]
                         当前要抢: f[i-2] + nums[i]

*/

class Solution {
    public int rob(int[] nums) {
        if (nums == null) return 0;

        for (int i = 1; i < nums.length; i++) {
            nums[i] = Math.max(nums[i-1], nums[i] + (i >=2 ? nums[i-2] : 0));
        }

        return nums[nums.length-1];
    }
}

// 1. 状态定义：f[i] 表示达到 i 所积累的💰
// 2. 状态计算：f[i] = MAX(f[0....i-2]) + v[i]
// 3. 边界：f[~] = 0

class Solution {
    public int rob(int[] nums) {
        if (nums == null || nums.length == 0) return 0;
        int prevMax = Integer.MIN_VALUE;
        for (int i = 0; i < nums.length; i++){
            if (i >= 2) {
                prevMax = Math.max(prevMax, nums[i-2]);
                nums[i] += prevMax;
            }
        }
        return Arrays.stream(nums).max().getAsInt();
    }
}