My 0ms dp solution using c++


  • -2
    A

    state A[i] represent room i must be robbed and robbe room of index less than i

    then A[i]=max{A[j],0}+nums[i] . 0<= j < i-1

    the result is max{A[i]}

        class Solution {
    public:
        int rob(vector<int>& nums) {
            int length=nums.size();
            int *A=new int[length];//A[i] represent the money of rob the room of i and less index.
            int maxMoney=0;
            for(int i=0;i<nums.size();i++)
            {
                A[i]=0;
                for(int j=0;j<i-1;j++)
                {
                    if(A[j]>A[i])
                        A[i]=A[j];
                }
                A[i]+=nums[i];
                if(A[i]>maxMoney)
                    maxMoney=A[i];
            }
            delete [] A;
            return maxMoney;
        }
    };

Log in to reply
 

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