Solution:DP O(n)


  • 2
    C

    DP function:F[i]=std::max(F[i-2]+num[i],F[i-1]),where i means the num from 0 to i,F means the maximum

    class Solution {
    public:
        int rob(vector<int> &num) {
            if (num.size()==0) return 0;
            if (num.size()==1) return num[0];
            if (num.size()==2) return std::max(num[0],num[1]);
            int len=num.size();
            vector<int> F(len,0);
            F[0]=num[0];
            F[1]=std::max(num[0],num[1]);
            for (int i=2;i<len;i++)
                F[i]=std::max(F[i-2]+num[i],F[i-1]);
            return F[len-1];
        }
    };

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.