Well Explained C++ Solution For DP Beginners


  • 0
    B
    public:
        int rob(vector<int>& nums) {
            int n=nums.size();
            int A[n+1],B[n+1];
            A[0]=0,B[0]=0;
            
            /*Take 2 Array of N+1 size
            A[i]: Money After Robed  ith House .
            B[i] : Money After skiped ith House.
            A[0]=0,B[0]=0;
            A[i] : will be Amount at B[i-1] plus money at i th house, becoz to rob i th house , U must not robed i-1 house
            
            B[i] = will be amount at A[i-1] , as you are skipping  i th house.
            B[i] = is max ( B[i-1] , A[i-1]) becoz there may be chance you are already having more money at B[i-1].
            
            for example: 2 1 1 2
            A: 0 -1 -1 -1 -1
            B: 0 -1 -1 -1 -1
            
            i = 1(first house)
            So have 2 options Robed or Skip.
            if Taken A[i] = B[i-1]+ 2
            A[1] = 2
            And if we skip
            B[1] = max(A[0], B[0]) = 0
            
            And so on iterate it for all the array
            
            finally max(maximum in A , maximum in B) is ANS.
            
            */
            for(int i=1;i<n+1;i++)
            {
                A[i]=B[i-1]+nums[i-1];
                
                B[i]=std::max(A[i-1],B[i-1]);
            }
            
            
            return max(A[n],B[n]);
            
            
        }
    };
    

Log in to reply
 

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