leetcode198. 打家劫舍

分析

由于不能投连续的两家，那么投第i家时，要么就不偷，要么就偷，投只能偷当前这家和i-2家，两种情况取最大值。即 f[i]=max(f[i-2]+nums[i],f[i-1])。

class Solution {
public:
    int rob(vector<int>& nums) {
        int n=nums.size();
        if(n==1)return nums[0];
        vector<int>f(n,0);//f[i]表示到第i家时的最大值。
        f[0]=nums[0],f[1]=max(nums[1],nums[0]);
        for(int i=2;i<n;i++){
            f[i]=max(f[i-2]+nums[i],f[i-1]);//要么偷第i家，要么不偷
        }
        return f[n-1];
    }
};