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

方法：动态规划

创建一个大小为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的最后一个元素即为最后的输出

时间复杂度：o(n)

空间复杂度：o(n)

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

        for (int i = 2; i <= nums.size(); i++) {
            dp[i] = max(dp[i - 1], dp[i - 2] + nums[i - 1]);
        }
        return dp[nums.size()];
    }
};