题目描述

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

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

样例1

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

样例2

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

算法

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

状态表示：

• $f[i]$ 表示从前$i$个数中选，所有选$nums[i]$的选法的最大值。
• $g[i]$ 表示从前$i$个数中选，所有不选$nums[i]$的选法的最大值。

状态计算：

• 如果当前数不选，上一个数选或不选任意，取最大值，即$f[i] = \max \{ f[i - 1], g[i - 1] \}$
• 如果当前数选，上一个数一定不选，即 $g[i] = f[i - 1] + nums[i-1]$
• 结果取最后两种状态的最大值，即$\max \{ f[n], g[n] \}$

举例：$[1, 2, 3, 1]$

时间复杂度

状态数为 $O(n)$，转移时间为 $O(1)$，故总时间复杂度为 $O(n)$。

空间复杂度

• 需要额外 $O(n)$ 的空间存储状态。
• 由于每个位置的状态只依赖于前一个位置的状态，故可以直接用一个变量表示状态，优化空间到常数。

C++ 代码

class Solution {
public:
    int rob(vector<int>& nums) {
        int n = nums.size();
        vector<int> f(n +  1), g(n + 1);  // f[i]表示从前i个数中选，所有不选nums[i]的选法的最大值，g[i]表示从前i个数中选，所有选nums[i]的选法的最大值，
        for(int i = 1; i <= n; i++)
        {
            f[i] = max(f[i - 1], g[i - 1]);  // 当前不选，上一个选或不选任意，取最大值
            g[i] = f[i - 1] + nums[i - 1];  // 当前选，上一个一定不选
        }
        return max(f[n], g[n]);  // 返回两种选法的最大值
    }
};

压缩空间优化后的一维DP：

class Solution {
public:
    int rob(vector<int>& nums) {
        int n = nums.size();
        int f = 0, g = 0;  // f表示从前i个数中选，所有不选nums[i]的选法的最大值，g表示从前i个数中选，所有选nums[i]的选法的最大值，
        for(int i = 1; i <= n; i++)
        {
            int last_f = f, last_g = g;  // 记录上一个数选和不选的状态
            f = max(last_f, last_g);  // 当前不选，上一个选或不选任意，取最大值
            g = last_f + nums[i - 1];  // 当前选，上一个一定不选
        }
        return max(f, g);  // 返回两种选法的最大值
    }
};