Share My 2ms C DP solution with O(1) space


  • 10
    Z

    f(j) indicates the robber has made a dicison for jth house for the max money, the recursion can be f(j) = max(f(j-1), f(j-2)+nums[j]); it can be implemented by iteration with O(1) space.

    #define max(x,y)  (((x)>(y))?(x):(y))
    int rob(int* nums, int numsSize) {
        int x0 = 0, x1 = 0, x2 = 0;
        
        //f(j) = max(f(j-1),f(j-2)+nums[i])
        for(int i = 0; i < numsSize; i++)
        {
            x2 = max(x0+nums[i],x1);
            x0 = x1;
            x1 = x2;
        }
        
        return x2;
    }

Log in to reply
 

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