My 3ms c++ solution


  • 0
    W
    class Solution {
        
    public:
        int rob(vector<int> &num) {
            int n=num.size();
            if(!n)
            {
                return 0;
            }
            return rob(num,n);
        }
        
        int rob(vector<int> &num, int n)
        {
            if(n==1)
            {
                return num[0];
            }
            else if(n==2)
            {
                return max(num[0],num[1]);
            }
            else
            {
                map<int, int>::iterator iter=record.find(n);
                if(iter!=record.end())
                {
                    return iter->second;
                }
                else
                {
                    int temp=max(num[n-1]+rob(num,n-2),rob(num,n-1));
                    record[n]=temp;
                    return temp;
                }
            }
        }
        
        map<int,int> record;
    };

Log in to reply
 

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