198. House robber

198_solution1_memo.c

#include <stdlib.h>

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

static int maxLoot(int idx, int *nums, int *memo) {
  if (idx == 0)
    return nums[0];
  if (idx == 1)
    return max(nums[0], nums[1]);

  if (memo[idx] != -1)
    return memo[idx];

  return memo[idx] =
             max(maxLoot(idx - 1, nums, memo),              // skip this house
                 maxLoot(idx - 2, nums, memo) + nums[idx]); // rob this house
}

int rob(int *nums, int numsSize) {
  int *memo = malloc(numsSize * sizeof(int));
  for (int i = 0; i < numsSize; i++)
    memo[i] = -1;
  int res = maxLoot(numsSize - 1, nums, memo);
  free(memo);
  return res;
}

198_solution2_tab.c

#include <stdlib.h>

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

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

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

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

198_solution1_memo.cpp

#include <algorithm>
#include <vector>

using namespace std;

class Solution {
public:
  vector<int> memo;

  int maxLoot(int idx, vector<int> &nums) {
    if (idx == 0)
      return nums[0];
    if (idx == 1)
      return max(nums[0], nums[1]);

    if (memo[idx] != -1)
      return memo[idx];

    return memo[idx] =
               max(maxLoot(idx - 1, nums),              // skip this house
                   maxLoot(idx - 2, nums) + nums[idx]); // rob this house
  }

  int rob(vector<int> &nums) {
    memo.assign(nums.size(), -1);
    return maxLoot(nums.size() - 1, nums);
  }
};

198_solution2_tab.cpp

#include <algorithm>
#include <vector>

using namespace std;

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

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

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

198_solution1_memo.go

package dp

func rob(nums []int) int {
    memo := make([]int, len(nums))
    for i := range memo {
        memo[i] = -1
    }

    var maxLoot func(idx int) int
    maxLoot = func(idx int) int {
        if idx == 0 {
            return nums[0]
        }
        if idx == 1 {
            return max(nums[0], nums[1])
        }

        if memo[idx] != -1 {
            return memo[idx]
        }

        memo[idx] = max(maxLoot(idx-1), // skip this house
            maxLoot(idx-2)+nums[idx]) // rob this house
        return memo[idx]
    }

    return maxLoot(len(nums) - 1)
}

198_solution2_tab.go

package dp

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

    dp := make([]int, n)
    dp[0] = nums[0]
    dp[1] = max(nums[0], nums[1])

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

198_solution1_memo.java

import java.util.Arrays;

class Solution {
    private int[] memo;

    private int maxLoot(int idx, int[] nums) {
        if (idx == 0)
            return nums[0];
        if (idx == 1)
            return Math.max(nums[0], nums[1]);

        if (memo[idx] != -1)
            return memo[idx];

        return memo[idx] = Math.max(maxLoot(idx - 1, nums), // skip this house
                maxLoot(idx - 2, nums) + nums[idx]); // rob this house
    }

    public int rob(int[] nums) {
        memo = new int[nums.length];
        Arrays.fill(memo, -1);
        return maxLoot(nums.length - 1, nums);
    }
}

198_solution2_tab.java

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

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

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

198_solution1_memo.js

/**
 * @param {number[]} nums
 * @return {number}
 */
var rob = function (nums) {
  const memo = new Array(nums.length).fill(-1);

  const maxLoot = (idx) => {
    if (idx === 0) return nums[0];
    if (idx === 1) return Math.max(nums[0], nums[1]);

    if (memo[idx] !== -1) return memo[idx];

    return (memo[idx] = Math.max(
      maxLoot(idx - 1), // skip this house
      maxLoot(idx - 2) + nums[idx], // rob this house
    ));
  };

  return maxLoot(nums.length - 1);
};

198_solution2_tab.js

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

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

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

198_solution1_memo.py

from typing import List


class Solution:
    def rob(self, nums: List[int]) -> int:
        memo = [-1] * len(nums)

        def max_loot(idx: int) -> int:
            if idx == 0:
                return nums[0]
            if idx == 1:
                return max(nums[0], nums[1])

            if memo[idx] != -1:
                return memo[idx]

            memo[idx] = max(
                max_loot(idx - 1),  # skip this house
                max_loot(idx - 2) + nums[idx],  # rob this house
            )
            return memo[idx]

        return max_loot(len(nums) - 1)

198_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]

        dp = [0] * n
        dp[0] = nums[0]
        dp[1] = max(nums[0], nums[1])

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

198_solution1_memo.rs

impl Solution {
    pub fn rob(nums: Vec<i32>) -> i32 {
        let mut memo = vec![-1; nums.len()];
        Self::max_loot(nums.len() - 1, &nums, &mut memo)
    }

    fn max_loot(idx: usize, nums: &[i32], memo: &mut Vec<i32>) -> i32 {
        if idx == 0 {
            return nums[0];
        }
        if idx == 1 {
            return nums[0].max(nums[1]);
        }

        if memo[idx] != -1 {
            return memo[idx];
        }

        memo[idx] = Self::max_loot(idx - 1, nums, memo) // skip this house
            .max(Self::max_loot(idx - 2, nums, memo) + nums[idx]); // rob this house
        memo[idx]
    }
}

198_solution2_tab.rs

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

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

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