Two DP O(n) solutions - C++


  • 0
    M
    int rob(vector<int>& nums) {        
            int p1 = 0, p2 = 0;
            
            for(int i = 0; i < nums.size(); ++i)
            {
                int curr = max(p1, nums[i] + p2);
                p2 = p1;
                p1 = curr;
            }
            
            return p1;
        }
    

    For each house you either have the choice of picking it or not picking it. If we pick it then we should not pick the adjacent element.

    Let us model as a recurrence. Let us denote F(i, j) as the maximum money we can rob considering elements in the range [i, j].

    Therefore we can write the recurrence as:

    F(i, j) = max{
         // rob house at position i, skip the adjacent
         nums[i] + F(i + 2, j),
         // don't rob house at position i
         F(i + 1, j)
    }
    

    With a base case of F(i, j) = 0 if i > n or j < 0.

    Our answer is defined when i = 0 and j = n - 1.

    As we can see, the function is not parameterized with j (j does not change). Alternatively we can model it in terms of j with i remaining constant, which is as follows:

    F(i, j) = max{
         // rob house at position j, skip the adjacent
         nums[j] + F(i, j - 2),
         // don't rob house at position j
         F(i, j - 1)
    }
    

    Now to write this bottom-up we must find a topological order to go through these states. With the second form we can do this by iterating j from 0 to n - 1, or with the first form we can process i from n - 1 to 0.

    Note that since we only care about the previous 2 states, we are only required to store them. Thus we can implement it with constant memory.


Log in to reply
 

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