class Solution { //https://www.youtube.com/watch?v=GrMBfJNk_NY&list=PLgUwDviBIf0qUlt5H_kiKYaNSqJ81PMMY&index=6&ab_channel=takeUforward public int rob(int[] nums) { int n = nums.length; //recursion // return solve1(nums ,n-1); //recursion + memoization // dp = new Integer[n]; // return solve2(nums , n-1); //tabulation -> 2*n | Sc - n 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 public int solve1(int nums[] , int idx){ if(idx == 0) return nums[0]; if(idx < 0 ) return 0; int pick = nums[idx] + solve1(nums ,idx-2); int notpick = 0 + solve1(nums , idx - 1); return Math.max(pick , notpick); } //recursion 2^n + memoization 2*n + Sc- n + n Integer dp[]; public int solve2(int nums[] , int idx){ if(idx == 0) return nums[0]; if(idx < 0 ) return 0; if(dp[idx] != null) return dp[idx]; int pick = nums[idx] + solve2(nums ,idx-2); int notpick = 0 + solve2(nums , idx - 1); 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