题目描述

你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。

给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。

样例

输入：[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 。

算法1

(动态规划) $O(n)$

状态变量:
变量do[i] 表示从索引0 的房子开始到索引i 的房子所偷取的最大金额。

状态计算:
如果打劫当前nums[i] + 隔着nums[i-1] 打劫之前家舍的总价格 > 不打劫当前nums[i],转而打劫nums[i-1] 与其之前的房子的总价格的话:
dp[i] = dp[i-2] + nums[i];
否则: dp[i] = dp[i-1]

初始条件:
dp[0] = nums[0] : 代表当前只有一家可以打劫的话,那就选择这家
dp[1] = Math.max(numns[0],nums[1]): 代表当前如果有两家可以打劫的话,选择金额最高的那家

时间复杂度

O(n)

参考文献

Java 代码

    public int rob(int[] nums) {
        int n = nums.length;
        if(n == 1) return nums[0];
        if(n == 2) return Math.max(nums[0],nums[1]);

        int[] dp = new int[n];
        dp[0] = nums[0]; //当只有一家的时候，就打劫这家
        dp[1] = Math.max(nums[0],nums[1]); //当有两家的时候,挑高价格的打劫
        for(int i = 2; i < n; i++){
            //比较下如果打劫当前nums[i] + 隔着nums[i-1] 打劫之前的总价格 与 不打劫当前nums[i],转而打劫nums[i-1] 与其之前的房子的总价格
           dp[i] = Math.max(nums[i] + dp[i-2],dp[i-1]);
        }     
        return dp[n-1];
    }

另一种写法:
状态变量:
f[i] 代表不打劫当前i 位置的最大值
g[i] 代表打劫当前i 位置的最大值

状态计算:
如果不打劫当前i 位置的最大值,那么就打劫i - 1以及其之前的家舍,而i-1 位置的最大值有两种可能: 要么是打劫了i- 1 位置的最大值,要么就是没有打劫i - 1 位置的最大值: Math.max(f[i-1],g[i-1]);

如果打劫了i 位置的最大值: g[i] = nums[i] + f[i-1] :当前nums[i] 的金额 + 没有打劫nums[i-1] 的最大值

class Solution {
        public int rob(int[] nums) {
        int n = nums.length;
        if(n == 1) return nums[0];
        if(n == 2) return Math.max(nums[0],nums[1]);

        //dp[1] = nums[0]
        //所以n+1 能够省去边界判断
        int[] f = new int[n+1]; //不打劫nums[i] 的最大值
        int[] g = new int[n+1]; //打劫nums[i] 的最大值
        for(int i = 1; i <= n; i++){
            f[i] = Math.max(f[i-1],g[i-1]);
            g[i] = nums[i-1] + f[i-1]; 
        }

        return Math.max(f[n],g[n]);
    }
}