DP 2ms C++, space O(1), concise with explaination


  • 8

    DP 2ms using C++, with/without memoization, concise solution with explaination

    Assume we start from left to right, then here I use dp array to store i-th house's max money I can squeeze. The idea is that since we cannot get a quote from adjacent house, the dp[i-1] can only be compared to discard or replace current position's max money. E.g. :

    For bonanzas like this:5=10=13= 1 = 7 = 2

    Will yield dp array like: 5=10=18=18=25=25<------then return the last element.

    The time complexity of DP straightforward version is O(n), space O(n).

    DP straightforward:

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

    This solution costs me 2ms.

    Since the dp array is only used with its newest two elements, we can reduce space using memoization. The idea is same with above solution except the dp array is replaced by int dp1, dp2. The time complexity is O(n), space O(1).

    dp with memoization:

    class Solution {
    public:
        int rob(vector<int> &A) {
            if(A.size()<=1)return A.empty()?0:A[0];
            int dp1=A[0],dp2=max(A[1],A[0]);
            for(int i=2;i<A.size();i++){
                swap(dp1,dp2);
                dp2=max(A[i]+dp2,dp1);
            }
            return dp2;
        }
    };
    

    This solution costs me 3ms.


Log in to reply
 

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