博客

198. 打家劫舍

【DP】非常经典的需要多少个不连续的DP问题，对于每个房屋要么拿要么不拿，所以定义状态dp[n + 1][2]，dp[i][0]表示当前第 i 个房间没有偷，那么他的最大金额就是上一个房间拿或者没拿的；而dp[i][1]表示当前第 i 个房间要偷，那么意味着上一个房间不能偷，所以是 dp[i – 1][0] + nums[i]。

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