题目

解法：动态规划

思路

动态规划，定义 dp[i][0/1] 表示前 i 个房屋在偷或不偷第 i 个房屋时的最大收益。

该问题的最优子结构性质体现在：对于第 i 个房屋，如果选择不偷，则最大收益为前 i-1 个房屋的最大收益（dp[i-1][0] 和 dp[i-1][1] 的较大值）；如果选择偷，则前一个房屋必须不偷，收益为 dp[i-1][0] + nums[i]。由于每个决策只依赖于前一个状态，且我们枚举了所有可能的选择，因此该动态规划方法能够得到全局最优解。

• Step 1: 初始化 dp[0][0] = 0（不偷第一个房屋），dp[0][1] = nums[0]（偷第一个房屋）
• Step 2: 遍历 i 从 1 到 n-1，计算 dp[i][0] = max(dp[i-1][0], dp[i-1][1])
• Step 3: 计算 dp[i][1] = dp[i-1][0] + nums[i]
• Step 4: 返回 max(dp[n-1][0], dp[n-1][1])

复杂度

• 时间复杂度: $O(n)$，其中 n 是房屋数量，只需一次遍历。
• 空间复杂度: $O(n)$，使用了二维数组 dp 存储状态（可优化至 $O(1)$）。

代码

class Solution {
public:
    int rob(vector<int>& nums) {
        int dp[nums.size()][2];
        memset(dp,0,sizeof(dp));
        dp[0][0] = 0;
        dp[0][1] = nums[0];
        for(int i = 1; i < nums.size(); i++){
            dp[i][0] = max(dp[i-1][0],dp[i-1][1]);
            dp[i][1] = dp[i-1][0]+nums[i];
        }
        return max(dp[nums.size()-1][0],dp[nums.size()-1][1]);
    }
};