House Robber

class Solution {
    /*本质上在一列数组中取出一个或多个不相邻数，使其和最大。那么我们对于这类求极值的问题首先考虑动态规划Dynamic Programming来解，我们维护一个一位数组dp，其中dp[i]表示到i位置时不相邻数能形成的最大和，经过分析，我们可以得到递推公式dp[i] = max(num[i] + dp[i - 2], dp[i - 1]),对于这种问题，找出递推公式是很重要的*/
public:
    int rob(vector<int>& nums) {
        int length=nums.size();
        if (length == 0)
        return  0;
        if (length == 1)
        return nums[0];
        if (length == 2)
        return max(nums[0],nums[1]);
        vector <int>dp={nums[0],max(nums[0],nums[1])};
        for (int i = 2;i<length;i++)
        dp.push_back(max(nums[i]+dp[i-2],dp[i-1]));
        return dp[length-1];
    }
};