Q-6 House Robber II - LeetCode 213
Sat Sep 09 2023 15:00:28 GMT+0000 (Coordinated Universal Time)
Saved by
@Ayush_dabas07
class Solution {
public int rob(int[] nums) {
//same question as house robber just circular array , both last index and first
//index cant be in 1 solution ....make 2 arrays for both and return max answer
// out of the two of them
int n = nums.length;
if(n == 1)
return nums[0];
int[] copy1 = Arrays.copyOfRange(nums, 0, n-1); //0 to n-2
int[] copy2 = Arrays.copyOfRange(nums, 1, n); //1 to n-1
//memoization solution
// return Math.max(solve(temp1 , n-2 , new Integer[n-1]) , solve(temp2 , n-2 , new Integer[n-1]));
return Math.max(solve2(copy1) ,solve2(copy2));
}
//tabulization from House Robber 1
public int solve2(int nums[]){
int n = nums.length;
int dp[]= new int[n];
dp[0] = nums[0];
for(int i = 1 ;i < n ; i++){
int pick = nums[i] + (i-2 >= 0 ? dp[i-2] : 0);
int notpick = 0 + dp[i-1];
dp[i] = Math.max(pick ,notpick);
}
return dp[n-1];
}
//recursion + memoization
public int solve(int[] nums , int idx , Integer[] dp){
if(idx == 0 )
return nums[0];
if(idx < 0)
return 0;
if(dp[idx] != null)
return dp[idx];
int pick = nums[idx] + solve(nums ,idx-2 , dp);
int notpick = 0 + solve(nums , idx-1 , dp);
return dp[idx] = Math.max(pick , notpick);
}
}
content_copyCOPY
https://leetcode.com/problems/house-robber-ii/
Comments