213. House robber II

213_solution1_memo.c

#include <stdlib.h>

static int max(int a, int b) { return a > b ? a : b; }

static int maxLoot(int idx, int start, int *nums, int *memo) {
  if (idx < start)
    return 0;
  if (memo[idx] != -1)
    return memo[idx];
  return memo[idx] = max(maxLoot(idx - 1, start, nums, memo),
                         maxLoot(idx - 2, start, nums, memo) + nums[idx]);
}

static void reset(int *memo, int n) {
  for (int i = 0; i < n; i++)
    memo[i] = -1;
}

int rob(int *nums, int numsSize) {
  int n = numsSize;
  if (n == 1)
    return nums[0];

  int *memo = malloc(n * sizeof(int));
  reset(memo, n);
  int skipLast = maxLoot(n - 2, 0, nums, memo);

  reset(memo, n); // reset: different subproblem
  int skipFirst = maxLoot(n - 1, 1, nums, memo);

  free(memo);
  return max(skipLast, skipFirst);
}

213_solution2_tab.c

#include <stdlib.h>

static int max(int a, int b) { return a > b ? a : b; }

// Max loot from houses start..end (inclusive), in a straight line
static int robRange(int *nums, int start, int end) {
  int len = end - start + 1;
  if (len == 1)
    return nums[start];

  int *dp = malloc(len * sizeof(int));
  dp[0] = nums[start];
  dp[1] = max(nums[start], nums[start + 1]);

  for (int i = 2; i < len; i++) {
    dp[i] = max(dp[i - 1],                    // skip this house
                dp[i - 2] + nums[start + i]); // rob this house
  }
  int res = dp[len - 1];
  free(dp);
  return res;
}

int rob(int *nums, int numsSize) {
  int n = numsSize;
  if (n == 1)
    return nums[0];

  return max(robRange(nums, 0, n - 2),  // exclude the last house
             robRange(nums, 1, n - 1)); // exclude the first house
}

213_solution1_memo.cpp

#include <algorithm>
#include <vector>

using namespace std;

class Solution {
  vector<int> memo;

  int maxLoot(int idx, int start, vector<int> &nums) {
    if (idx < start)
      return 0;
    if (memo[idx] != -1)
      return memo[idx];
    return memo[idx] = max(maxLoot(idx - 1, start, nums),
                           maxLoot(idx - 2, start, nums) + nums[idx]);
  }

public:
  int rob(vector<int> &nums) {
    int n = nums.size();
    if (n == 1)
      return nums[0];

    memo.assign(n, -1);
    int skipLast = maxLoot(n - 2, 0, nums);

    memo.assign(n, -1); // reset: different subproblem
    int skipFirst = maxLoot(n - 1, 1, nums);

    return max(skipLast, skipFirst);
  }
};

213_solution2_tab.cpp

#include <algorithm>
#include <vector>

using namespace std;

class Solution {
  // Max loot from houses start..end (inclusive), in a straight line
  int robRange(vector<int> &nums, int start, int end) {
    int len = end - start + 1;
    if (len == 1)
      return nums[start];

    vector<int> dp(len);
    dp[0] = nums[start];
    dp[1] = max(nums[start], nums[start + 1]);

    for (int i = 2; i < len; i++) {
      dp[i] = max(dp[i - 1],                    // skip this house
                  dp[i - 2] + nums[start + i]); // rob this house
    }
    return dp[len - 1];
  }

public:
  int rob(vector<int> &nums) {
    int n = nums.size();
    if (n == 1)
      return nums[0];

    return max(robRange(nums, 0, n - 2),  // exclude the last house
               robRange(nums, 1, n - 1)); // exclude the first house
  }
};

213_solution1_memo.go

package dp

func rob(nums []int) int {
    n := len(nums)
    if n == 1 {
        return nums[0]
    }

    memo := make([]int, n)
    reset := func() {
        for i := range memo {
            memo[i] = -1
        }
    }

    var maxLoot func(idx, start int) int
    maxLoot = func(idx, start int) int {
        if idx < start {
            return 0
        }
        if memo[idx] != -1 {
            return memo[idx]
        }
        memo[idx] = max(maxLoot(idx-1, start), maxLoot(idx-2, start)+nums[idx])
        return memo[idx]
    }

    reset()
    skipLast := maxLoot(n-2, 0)

    reset() // reset: different subproblem
    skipFirst := maxLoot(n-1, 1)

    return max(skipLast, skipFirst)
}

213_solution2_tab.go

package dp

// robRange returns the max loot from houses start..end (inclusive), in a straight line
func robRange(nums []int, start, end int) int {
    length := end - start + 1
    if length == 1 {
        return nums[start]
    }

    dp := make([]int, length)
    dp[0] = nums[start]
    dp[1] = max(nums[start], nums[start+1])

    for i := 2; i < length; i++ {
        dp[i] = max(dp[i-1], // skip this house
            dp[i-2]+nums[start+i]) // rob this house
    }
    return dp[length-1]
}

func rob(nums []int) int {
    n := len(nums)
    if n == 1 {
        return nums[0]
    }

    return max(robRange(nums, 0, n-2), // exclude the last house
        robRange(nums, 1, n-1)) // exclude the first house
}

213_solution1_memo.java

import java.util.Arrays;

class Solution {
    private int[] memo;

    private int maxLoot(int idx, int start, int[] nums) {
        if (idx < start)
            return 0;
        if (memo[idx] != -1)
            return memo[idx];
        return memo[idx] = Math.max(maxLoot(idx - 1, start, nums),
                maxLoot(idx - 2, start, nums) + nums[idx]);
    }

    public int rob(int[] nums) {
        int n = nums.length;
        if (n == 1)
            return nums[0];

        memo = new int[n];
        Arrays.fill(memo, -1);
        int skipLast = maxLoot(n - 2, 0, nums);

        Arrays.fill(memo, -1); // reset: different subproblem
        int skipFirst = maxLoot(n - 1, 1, nums);

        return Math.max(skipLast, skipFirst);
    }
}

213_solution2_tab.java

class Solution {
    // Max loot from houses start..end (inclusive), in a straight line
    private int robRange(int[] nums, int start, int end) {
        int len = end - start + 1;
        if (len == 1)
            return nums[start];

        int[] dp = new int[len];
        dp[0] = nums[start];
        dp[1] = Math.max(nums[start], nums[start + 1]);

        for (int i = 2; i < len; i++) {
            dp[i] = Math.max(dp[i - 1], // skip this house
                    dp[i - 2] + nums[start + i]); // rob this house
        }
        return dp[len - 1];
    }

    public int rob(int[] nums) {
        int n = nums.length;
        if (n == 1)
            return nums[0];

        return Math.max(robRange(nums, 0, n - 2), // exclude the last house
                robRange(nums, 1, n - 1)); // exclude the first house
    }
}

213_solution1_memo.js

/**
 * @param {number[]} nums
 * @return {number}
 */
var rob = function (nums) {
  const n = nums.length;
  if (n === 1) return nums[0];

  let memo;
  const maxLoot = (idx, start) => {
    if (idx < start) return 0;
    if (memo[idx] !== -1) return memo[idx];
    return (memo[idx] = Math.max(
      maxLoot(idx - 1, start),
      maxLoot(idx - 2, start) + nums[idx],
    ));
  };

  memo = new Array(n).fill(-1);
  const skipLast = maxLoot(n - 2, 0);

  memo = new Array(n).fill(-1); // reset: different subproblem
  const skipFirst = maxLoot(n - 1, 1);

  return Math.max(skipLast, skipFirst);
};

213_solution2_tab.js

/**
 * @param {number[]} nums
 * @return {number}
 */
var rob = function (nums) {
  const n = nums.length;
  if (n === 1) return nums[0];

  // Max loot from houses start..end (inclusive), in a straight line
  const robRange = (start, end) => {
    const len = end - start + 1;
    if (len === 1) return nums[start];

    const dp = new Array(len);
    dp[0] = nums[start];
    dp[1] = Math.max(nums[start], nums[start + 1]);

    for (let i = 2; i < len; i++) {
      dp[i] = Math.max(
        dp[i - 1], // skip this house
        dp[i - 2] + nums[start + i], // rob this house
      );
    }
    return dp[len - 1];
  };

  return Math.max(
    robRange(0, n - 2), // exclude the last house
    robRange(1, n - 1), // exclude the first house
  );
};

213_solution1_memo.py

from typing import List


class Solution:
    def rob(self, nums: List[int]) -> int:
        n = len(nums)
        if n == 1:
            return nums[0]

        def max_loot(idx: int, start: int) -> int:
            if idx < start:
                return 0
            if memo[idx] != -1:
                return memo[idx]
            memo[idx] = max(
                max_loot(idx - 1, start), max_loot(idx - 2, start) + nums[idx]
            )
            return memo[idx]

        memo = [-1] * n
        skip_last = max_loot(n - 2, 0)

        memo = [-1] * n  # reset: different subproblem
        skip_first = max_loot(n - 1, 1)

        return max(skip_last, skip_first)

213_solution2_tab.py

from typing import List


class Solution:
    def rob(self, nums: List[int]) -> int:
        n = len(nums)
        if n == 1:
            return nums[0]

        def rob_range(start: int, end: int) -> int:
            """Max loot from houses start..end (inclusive), in a straight line."""
            length = end - start + 1
            if length == 1:
                return nums[start]

            dp = [0] * length
            dp[0] = nums[start]
            dp[1] = max(nums[start], nums[start + 1])

            for i in range(2, length):
                dp[i] = max(
                    dp[i - 1],  # skip this house
                    dp[i - 2] + nums[start + i],  # rob this house
                )
            return dp[length - 1]

        return max(
            rob_range(0, n - 2),  # exclude the last house
            rob_range(1, n - 1),  # exclude the first house
        )

213_solution1_memo.rs

impl Solution {
    pub fn rob(nums: Vec<i32>) -> i32 {
        let n = nums.len();
        if n == 1 {
            return nums[0];
        }

        let mut memo = vec![-1; n];
        let skip_last = Self::max_loot(n as i32 - 2, 0, &nums, &mut memo);

        memo.fill(-1); // reset: different subproblem
        let skip_first = Self::max_loot(n as i32 - 1, 1, &nums, &mut memo);

        skip_last.max(skip_first)
    }

    // idx is i32 so idx - 2 can drop below start without underflow
    fn max_loot(idx: i32, start: i32, nums: &[i32], memo: &mut Vec<i32>) -> i32 {
        if idx < start {
            return 0;
        }
        let i = idx as usize;
        if memo[i] != -1 {
            return memo[i];
        }
        memo[i] = Self::max_loot(idx - 1, start, nums, memo)
            .max(Self::max_loot(idx - 2, start, nums, memo) + nums[i]);
        memo[i]
    }
}

213_solution2_tab.rs

impl Solution {
    pub fn rob(nums: Vec<i32>) -> i32 {
        let n = nums.len();
        if n == 1 {
            return nums[0];
        }

        Self::rob_range(&nums, 0, n - 2) // exclude the last house
            .max(Self::rob_range(&nums, 1, n - 1)) // exclude the first house
    }

    // Max loot from houses start..end (inclusive), in a straight line
    fn rob_range(nums: &[i32], start: usize, end: usize) -> i32 {
        let len = end - start + 1;
        if len == 1 {
            return nums[start];
        }

        let mut dp = vec![0; len];
        dp[0] = nums[start];
        dp[1] = nums[start].max(nums[start + 1]);

        for i in 2..len {
            dp[i] = dp[i - 1] // skip this house
                .max(dp[i - 2] + nums[start + i]); // rob this house
        }
        dp[len - 1]
    }
}