# C++ DP 0ms with detailed explanation

• 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];
}
};
``````

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