Leetcode-打家劫舍（中等）

题目描述

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

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

动态规划
dp[i]表示最后一个偷i号房间时能拿到的最多金额 从0号房间开始
dp[i]=max(dp[i-j]+nums[i]) j从2开始，递增到i-j=0 易错点：记得要加i本身的金额nums[i]
需要注意的是：最后判断一下偷到最后一个房间停止和偷到倒数第二个房间停止 哪个更高 eg:(1,3,1) 此时偷3>1+1

class Solution {
public:
    int rob(vector<int>& nums) {
        int len = nums.size();
        if (len == 1) return nums[0];
        vector<int> dp(len, 0);
        dp[0] = nums[0];
        dp[1] = nums[1];
        for (int i = 2; i <= len - 1; i++) {
            for (int j = 2; i - j >= 0; j++) {
                dp[i] = max(dp[i], dp[i - j] + nums[i]);//记得加自己房间对应的钱
            }
        }

        return max(dp[len - 1], dp[len - 2]);//最后需要判断一下哪个更大  如（1,3,1）不放心的话遍历dp找最大值也是可以的
    }
};