Hi, this is Shunchi!

  • Home

  • Tags0

  • Archives267

  • Categories0

  • Curricula

  • DSA

  • LeetCode_Notes

  • Interviews

  • General

  • Resume

198. House Robber

Posted on 2020-03-31 | Edited on 2021-01-22

https://leetcode.com/problems/house-robber/

DP

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class 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 link
1
2
3
4
5
6
7
8
9
10
11
class 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;
}
}

<1…244245246…267>
ShunchiZhou

ShunchiZhou

267 posts
RSS
GitHub E-Mail Gitbook Linkedin
© 2024 ShunchiZhou
Powered by Hexo v5.4.0
|
0%