题解 | #打家劫舍(二)#

方法：动态规划

创建一个大小为nums.size() + 1的数组dp，dp[i]表示以nums[i - 1]结尾的数组的最大金额，对于dp[i]有两种情况，可以选择偷或者不偷：

选择偷：dp[i] = dp[i - 2] + nums[i - 1];

选择不偷：dp[i] = dp[i - 1]。选取两个中的最大值即为当前的最大金额。

将问题分解为偷第一家和不偷第一家两种情况讨论：

偷第一家：dp[1] = nums[0]，函数的输出为dp[nums.size() - 1]

不偷第一家：dp[1] = 0，函数的输出为dp[nums.size()]

时间复杂度：o(n)

空间复杂度：o(n)

class Solution {
  public:
    int rob(vector<int>& nums) {
        int len = nums.size();
        vector<int> dp(len + 1, 0);

        // 偷第一家
        dp[1] = nums[0];
        for (int i = 2; i < len; i++) {
            dp[i] = max(dp[i - 1], nums[i - 1] + dp[i - 2]);
        }
        int res = dp[len - 1];
        // 不偷第一家
        dp[1] = 0;
        for (int i = 2; i <= len; i++) {
            dp[i] = max(dp[i - 1], nums[i - 1] + dp[i - 2]);
        }
        res = max(res, dp[len]);

        return res;
    }
};