leetcode：198. 打家劫舍

题目

你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。
给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。

示例：

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

解答 & 代码

动态规划：

动态规划数组 **dp**：dp[i] 代表第 0~i 间房屋能抢劫的最高金额
状态转移方程：**dp[i] = max(dp[i-2] + nums[i], dp[i-1])**
- dp[i - 2] + nums[i]：dp[i - 2] 是抢劫了第 0~i-2 间房屋的最高金额，没有抢第 i-1 间房间，因此还能抢劫第 i 间房屋（金额 nums[i]）
- dp[i - 1]：是抢劫了第 0~i-1 间房屋的最高金额，第 i-1 间房屋可能被抢了，因此不能再能抢劫第 i 间房屋
  
  上面有个问题：是抢劫了第 0~i-1 间房屋的最高金额，第 i-1 间房屋只是可能被抢了，但也可能没有抢，如果没有抢，那理论上还能抢劫第 i 间房屋，所以这种情况下应该 dp[i] = max(dp[i-2] + nums[i], dp[i-1] + nums[i]) 才对。But，如果第 i-1 间房屋没有被抢，那么 dp[i-1] = dp[i-2]，所以 max(dp[i-2] + nums[i], dp[i-1]) = max(dp[i-2] + nums[i], dp[i-2]) = dp[i-2] + nums[i]，max(dp[i-2] + nums[i], dp[i-1] + nums[i]) = max(dp[i-2] + nums[i], dp[i-2] + nums[i]) = dp[i-2] + nums[i]，所以其实是等价的，没有影响
初始化：
- dp[0] = nums[0]
- dp[1] = max(nums[0], nums[1])

每个状态 dp[i] 只和前两个状态 dp[i-2], dp[i-1] 有关，因此可以只用两个状态变量，而无需 dp 数组

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

复杂度分析：

时间复杂度 O(N)
空间复杂度 O(1)

执行结果：

执行结果：通过
执行用时：0 ms, 在所有 C++ 提交中击败了 100.00% 的用户
内存消耗：7.4 MB, 在所有 C++ 提交中击败了 77.26% 的用户

hot 100

[中等] 198. 打家劫舍

题目

解答 & 代码