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); } }
Preview:
downloadDownload PNG
downloadDownload JPEG
downloadDownload SVG
Tip: You can change the style, width & colours of the snippet with the inspect tool before clicking Download!
Click to optimize width for Twitter