https://leetcode.com/problems/house-robber/
DP1
2
3
4
5
6
7
8
9
10
11
12
13
14class Solution {
int[] memo;
public int rob(int[] nums) {
memo = new int[nums.length];
Arrays.fill(memo, -1);
return rob(nums, nums.length - 1);
}
private int rob(int[] nums, int i) {
if (i < 0) return 0;
if(memo[i]<0) memo[i]= Math.max(rob(nums, i - 2) + nums[i], rob(nums, i - 1));
return memo[i];
}
}
DP without array link1
2
3
4
5
6
7
8
9
10
11class Solution {
public int rob(int[] nums) {
int prevMax=0,currMax=0;
for(int x:nums){
int tmp=currMax;
currMax=Math.max(prevMax+x,currMax);
prevMax=tmp;
}
return currMax;
}
}