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