House Robber II – How to rob houses efficiently.

https://leetcode.com/problems/house-robber-ii/

We are not actually talking about robbing real house here.

The problem is:

You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed. All houses at this place are arranged in a circle. That means the first house is the neighbor of the last one. Meanwhile, 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.

Example 1:
Input: [2,3,2] Output: 3 Explanation: You cannot rob house 1 (money = 2) and then rob house 3 (money = 2), because they are adjacent houses.
Example 2:
Input: [1,2,3,1] Output: 4 Explanation: Rob house 1 (money = 1) and then rob house 3 (money = 3). Total amount you can rob = 1 + 3 = 4.

So it is an optimization problem over a set of discrete items with a rule that helps us to easily make out a relationship equation. The problem is begging you to use dynamic programming.

dp[i] = max(dp[i-1],dp[i-2]+value[i])

But how do you account for the circle part of the problem? Note that if you pick the first house, the last house is untouchable, and vice versa. So the problem is actually split into two smaller problems: finding the optimized value for the subset 0..n-2, and subset 1..n-1.

class Solution {
     fun rob(nums: IntArray): Int {
         val n = nums.size
         //Check boundaries
         if (n==0) return 0
         if (n==1) return nums[0]
         if (n==2) return Math.max(nums[0],nums[1])
         //Initiates variables and base cases
         var dp = IntArray(nums.size)
         var dp2 = IntArray(nums.size)
         dp[0] = nums[0]
         dp[1] = Math.max(nums[0],nums[1])
         dp2[n-1] = nums[n-1]
         //Fill up the tables
         dp2[n-2] = Math.max(nums[n-1],nums[n-2])
         for (i in 2..n-2) {
             dp[i] = Math.max(dp[i-1],dp[i-2]+nums[i])
         }
         for (i in n-3 downTo 1) {
             dp2[i] = Math.max(dp2[i+1],dp2[i+2]+nums[i])
         }
         return Math.max(dp[n-2],dp2[1])
     }
 }

This piece of code can be prettified further though.

class Solution {
    fun rob(nums: IntArray): Int {
        val n = nums.size
        //Check boundaries
        if (n==0) return 0
        if (n==1) return nums[0]
        if (n==2) return Math.max(nums[0], nums[1])
        //Initiates variables and base cases
        return Math.max(regularRob(nums, 0, n-2), 
                        regularRob(nums, 1, n-1))
    }
    
    fun regularRob(nums:IntArray, begin:Int, end:Int): Int {
        //Assert:begin - end>=2
        var dp = IntArray(nums.size)
        dp[begin] = nums[begin]
        dp[begin+1] = Math.max(nums[begin], nums[begin+1])
        //Fill up the tables
        for (i in begin+2..end) {
            dp[i] = Math.max(dp[i-1], dp[i-2] + nums[i])
        }
        return dp[end]
    }
}