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

方法1：动态规划，f(k)=max{f(k−1),H(k)​+f(k−2)}，f(k)表示前k个房子能偷到最大金额，H(k)表示第k个房子存放金额

class Solution {
public:
    int rob(vector<int>& nums) {
        vector<int>dp(nums.size()+1,0);
        dp[0] = 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()];
    }
};

方法2：动态规划空间优化，计算 f(n) 的时候，只用到了 f(n−1) 和 f(n−2) 的结果。n−2之前的子问题，已经用不到了，所以不需要用数组来存储dp数据

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