# The correct DP solution

• Here is the DP formula that leads to the right answer:

• M(k) = money at the kth house
• P(0) = 0
• P(1) = M(1)
• P(k) = max(P(k−2) + M(k), P(k−1))

• ``````class Solution(object):
def rob(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
n = len(nums)
if(n == 0):
return 0
if(n == 1):
return nums[0]
money = [0] * n
money[0] = nums[0]

m1 = max(money[0], nums[1])
money[1] = m1

if(n <= 2):
return money[n - 1]
for i in range(2, n):
m1 = money[i - 1]
m2 = money[i - 2] + nums[i]
money[i]= max(m1, m2)

return money[n - 1]``````

• This is good, but since you don't need to reconstruct the actual solution, you could reduce it to O(1) space.

• Thanks for the recursion, really simplified what I was coming up with.

• Seems over time limit.

``````/* M(k) = money at the kth house */
/* P(0) = 0 */
/* P(1) = M(1) */
/* P(k) = max(P(k−2) + M(k), P(k−1)) */
class Solution {
public:
unordered_map<int, int> cache;
int dp(vector<int>& nums, int i) {
if(i < 0)
return 0;
else if(i == 0)
return nums[0];
else if(cache[i])
return cache[i];
else {
int tmp = max(dp(nums, i-2)+nums[i], dp(nums, i-1));
cache[i] = tmp;
return tmp;
}
}
int rob(vector<int>& nums) {
return dp(nums, nums.size()-1);
}
};
``````

• ``````class Solution {
public:
int rob(vector<int>& nums) {
if (nums.size() == 0)
return 0;

int len = nums.size();
vector<int> res;
res.push_back(0);
res.push_back(nums[0]);

int maxPro = max(res[0], res[1]);

for (int i = 1; i < len; i++) {
int present = max(res[i-1] + nums[i], res[i]);;
res.push_back(present);

if (present > maxPro)
maxPro = present;
}

return maxPro;
}
};
``````

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