0ms C++ dp solution with explanation


  • 1
    T

    robs(k) = max( robs(k-2), rob(k-3) ) + nums(k);

    In the 1st pass, I didn't calculate the N-1 element;

    In the 2nd pass, I didn't calculate the N-2 element;

    The final result is the max of the two pass.

    class Solution {
    public:
        int rob(vector<int>& nums) {
            const int N = nums.size();
            if(0 == N) return 0;
            if(1 == N) return nums[0];
            if(2 == N) return max(nums[0], nums[1]);
            if(3 == N) return max(max(nums[0], nums[1]), nums[2]);
            vector<int> robs(N, 0);
    
            //the 1st pass
            robs[0] = nums[0];
            robs[1] = nums[1];
            robs[2] = nums[0] + nums[2];
            for(int i = 3; i < N -1;  ++i){
                robs[i] = max(robs[i-2], robs[i-3]) + nums[i];
            }
            int max1 = max(robs[N-2], robs[N-3]);
    
            //the 2nd pass
            robs[0] = nums[0];
            robs[1] = nums[1] + nums[N-1];
            robs[2] = max(nums[0], nums[N-1]) + nums[2];
            for(int i = 3; i < N -2;  ++i){
                robs[i] = max(robs[i-2], robs[i-3]) + nums[i];
            }
            int max2 = max(robs[N-3], robs[N-4]);
            return max(max1, max2);
        }
    };

Log in to reply
 

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