198. House Robber

You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them is that adjacent houses have security systems connected and it will automatically contact the police if two adjacent houses were broken into on the same night.

Given an integer array nums representing the amount of money of each house, return the maximum amount of money you can rob tonight without alerting the police.

Example: 1

Input: nums = [1,2,3,1]

Output: 4

Example: 2

Input: nums = [2,7,9,3,1]

Output: 12

Constraints:

• 1 <= nums.length <= 100
• 0 <= nums[i] <= 400

Solving using recursion:

• Let's consider we are at index i.
• We can choose to do two things from here.
• Either we can take this element (at i^th position) and go to element after the next element (i.e i + 2). This is because we are not allowed to take adjacent elements.
• Or, we can ignore this element and go to the next element (i.e i + 1).
• Also we should consider that if our current index goes out of array, we should return 0, because there is no element out there.

Recursion code (TLE): class Solution { public int rob(int[] nums) { return recur(0, nums); } int recur(int idx, int[] nums) { // handling base case if(idx >= nums.length) { return 0; } // taking the paths as discussed above // taking current element and going to (i + 2) // going to (i + 1) by ignoring the current element return Math.max(nums[idx] + recur(idx + 2, nums), recur(idx + 1, nums)); } }

Solving using DP:

• Now we will cache the result at every index that we get after solving the subproblem.
• This will reduce our recomputations, and will help us to get Accepted :)

DP code (TLE to Accepted): class Solution { // creating an array to store result of subproblem Integer[] dp; public int rob(int[] nums) { dp = new Integer[nums.length]; return recur(0, nums); } int recur(int idx, int[] nums) { if(idx >= nums.length) { return 0; } // checking if we have already solved the subproblem // if yes, we will return it as a result if(dp[idx] != null) { return dp[idx]; } // storing the result of the current subproblem // so that it can be used later on dp[idx] = Math.max(nums[idx] + recur(idx + 2, nums), recur(idx + 1, nums)); return dp[idx]; } }