# C++ DP solution with thinking process explanation

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

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