How to use recursion to exit correctly for House Robber implementation?

Question

I'm doing the House Robber challenge.

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 system connected and it will automatically contact the police if two adjacent houses were broken into on the same night.

Given a list of non-negative integers representing the amount of money of each house, determine the maximum amount of money you can rob tonight without alerting the police.

My code:

class Solution {
    func rob(_ nums: [Int]) -> Int {
        var mostMoneyRobbed = 0

        func rob(neighborUnits: [Int], startfromUnit unit: Int, didRobAdjacentUnit: Bool, totalMoneyRobbed total: Int){

            if total > mostMoneyRobbed{
                mostMoneyRobbed = total
            }
            for i in unit...neighborUnits.count - 1{
                if i == neighborUnits.count - 1{
                    if !didRobAdjacentUnit{
                        if total + nums[i] > mostMoneyRobbed{                                
                            mostMoneyRobbed = total + nums[i]                                
                        }
                    }
                    return
                }

                if didRobAdjacentUnit{
                    rob(neighborUnits: nums, startfromUnit: unit + 1, didRobAdjacentUnit: false, totalMoneyRobbed: total)
                }else{
                    rob(neighborUnits: nums, startfromUnit: unit + 1, didRobAdjacentUnit: true, totalMoneyRobbed: total + nums[i])
                    rob(neighborUnits: nums, startfromUnit: unit + 1, didRobAdjacentUnit: false, totalMoneyRobbed: total)
                }
            }            
        }
        guard nums.count > 0 else {
            return 0
        }

        rob(neighborUnits: nums, startfromUnit: 0, didRobAdjacentUnit: true, totalMoneyRobbed: 0)
        rob(neighborUnits: nums, startfromUnit: 0, didRobAdjacentUnit: false, totalMoneyRobbed: 0)

        return mostMoneyRobbed
    }
}

Usage:

let s = Solution()
print(s.rob([1,2,3])) // returns 5 instead of 4 

---

My iteration strategy is:

• if the previous has was robbed then I can only not rob at my next iteration.
• if the previous has was not robbed then I can either rob or not at my next iteration. Obviously to find all valid robberies I do both!

My exit strategy is done at the line below:

if i == neighborUnits.count - 1{

basically if I reach the end of the units the iteration will stop.

Then I compare the value with mostMoneyRobbed and if it's bigger I set my value to that. At the end of the loop I just return mostMoneyRobbed

yet after reach the last element of the block and returning my code continues to proceed!!!! I don't understand why. It should be something very trivial

Kindly note I don't want alternate solutions. I want to fix my own implementation.

Answer 1

You can follow the DP approach to solve the time limit exceeded problem. As it will remove unnecessary recursive calls as we are storing in DP you can create one DP array and store the already computed results in the DP array and compare the max amount if we add the new amount to the previous one is greater than the amount currently available. like this max(dp[index - 2] + nums[index], dp[index - 1]).

    class Solution {
    func rob(_ nums: [Int]) -> Int {
        
        if nums.count == 0 {
            return 0
        }
        
        if nums.count == 1 {
            return nums[0]
        }
        
        if nums.count == 2 {
            return max(nums[0], nums[1])
        }
        
        var dp = [Int]()
        dp.append(nums[0])
        dp.append(max(nums[0], nums[1]))
        for index in 2..<nums.count {
            dp.append(max(dp[index - 2] + nums[index], dp[index - 1]))
        }
        return dp[nums.count - 1]
    }
    
}