C++ DP solution with thinking process explanation


  • 4
    H

    Following the same logic described in a post about Best Time to Buy and Sell Stock with Cooldown, we could try to solve this problem with DP.

    Define the following variables

    rob[i] means max profit for any robbing sequence before house i ending with rob
    rest[i] mean max profit for any robbing sequence before house i ending with rest

    We could get the following relationship,

    rob[i]  = max(rob[i-1], rest[i-1] + value)
    rest[i] = max(rest[i-1], rob[i-1])
    

    Furthermore, we always gain more profit when robbing the house. As a result,

    rob[i] > rest[i]
    rest[i] = rob[i-1]
    

    substitute these into the original equations, we get

    rob[i]  = max(rob[i-1], rob[i-2] + value)
    

    So we only need two values to keep track of the max profit.

    class Solution {
    public:
        int rob(vector<int>& nums) {
            auto best = 0, prev_best = 0;
            for(auto num : nums)
            {
                auto pbest = best;
                best = max(best, prev_best + num);
                prev_best = pbest;
            }
            return best;
        }
    };
    

Log in to reply
 

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