Share my C++ DP sol


  • 5
    M

    Say num.size() == n. Define f(i) be maximum sum from i to n-1 for the case you rob house i. Define g(i) be maximum sum from i to n-1 for the case that you do not rob house i. Therefore,

    f(i) = num[i] + g(i+1) <--- rob house i plus the max sum of the case
    that you do not rob house i+1

    g(i) = max(f(i+1),g(i+1)) <--- do not rob house i. Get either the
    maximum sum of the case you rob house i+1, or of the case you do not
    rob house i+1

    You do this backwards from the last house and the final answer is max(f(0),g(0)).

    The code:

    int rob(vector<int>& nums) {
            int f=0, g=0;
            for(int i=nums.size()-1; i>=0; i--) {
                int f_nxt = nums[i] + g;
                int g_nxt = max(f,g);
                f = f_nxt;
                g = g_nxt;
            }
            return max(f,g);
        }

Log in to reply
 

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