House Robber

April 07, 2015

Reading time ~1 minute

水水的动归

很容易想到DP 然后 f[i] = max(f[i-1],f[i-2] + num[i]);

class Solution {
public:
    int rob(vector<int> &num) {
        //f[i] = max(f[i-1],f[i-2]+num[i])
        if(num.size() <= 1) return num.empty() ? 0 : num[0];
        vector<int> f = {num[0],max(num[0],num[1])};
        for(int i = 2 ; i < num.size() ; i++)
        {
            f.push_back(max(f[i-1],f[i-2]+num[i]));
        }
        return f.back();
    }
};