C++ DP 0ms with detailed explanation


  • 0
    Y
    • Use two tables sum1 and sum2 to store the total money robbed:
    • sum1[i]: total money when robbing the first i houses, and the i-th house is robbed;
    • sum2[i]: total money when robbing the first i houses, but the i-th is NOT robbed.
    • Since two adjacent houses can NOT be robbed, we have the following:
    • (1) sum1[i] = sum2[i-1] + nums[i];
    • (2) sum2[i] = max{sum1[i-1], sum2[i-1]}.
    • (1) means that, the total money of robbing the first i houses (with the i-th robbed) = the total money of robbing the first i-1 houses (with the (i-1)-th not robbed) + money robbed from the i-th house;
    • (2) means that, the total money of robbing the first i houses (with the i-the NOT robbed) = the total money of robbing the first i-1 houses (either the (i-1)-th robbed or not, take whatever with more money).
    class Solution {
    public:
        int rob(vector<int>& nums) {
            int n = nums.size();
            if (n == 0) return 0;
            int sum1[n], sum2[n];
            sum1[0] = nums[0]; //only one house there and house 0 is robbed
            sum2[0] = 0; //only one house there and hourse 0 is NOT robbed
            for (int i = 1; i < n; ++i)
            {
                sum1[i] = sum2[i-1] + nums[i];
                sum2[i] = max(sum1[i-1], sum2[i-1]);
            }
            return sum1[n-1] > sum2[n-1] ? sum1[n-1] : sum2[n-1];
        }
    };
    

Log in to reply
 

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