Problem of The Day: House Robber

Problem Statement

leetcode problem link

My Solution [Accepted]

class Solution:
    def rob(self, nums: List[int]) -> int:
        memo = {}
        def dp(i, curr):
            if (i, curr) in memo:
                return memo[(i, curr)]
            if i >= len(nums):
                return curr

            rob_now = dp(i + 2, curr + nums[i])
            skip = dp(i + 1, curr)
            memo[(i, curr)] = max(rob_now, skip)
            return memo[(i, curr)]

        return dp(0, 0)

public class Solution {
    public Dictionary<(int, int), int> Memo { set; get; } = new Dictionary<(int, int), int>();

    public int helper(int i, int current, int[] nums) {
        if (Memo.ContainsKey((i, current))) {
            return Memo[(i, current)];
        }
        if (i >= nums.Length) {
            return current;
        }
        var robNow = helper(i + 2, current + nums[i], nums);
        var skip = helper(i + 1, current, nums);
        Memo[(i, current)] = Math.Max(robNow, skip);
        return Memo[(i, current)];
    }

    public int Rob(int[] nums) {
        return helper(0, 0, nums);
    }
}

Improve Algorithm

public class Solution {
    // We only need to memoize the index 'i'
    private int[] _memo;

    public int Rob(int[] nums) {
        _memo = new int[nums.Length];
        Array.Fill(_memo, -1); // Initialize with -1 to represent "uncalculated"
        return Helper(0, nums);
    }

    private int Helper(int i, int[] nums) {
        if (i >= nums.Length) return 0;
        if (_memo[i] != -1) return _memo[i];

        // Decision: Rob this house (and skip next) OR skip this house
        int rob = nums[i] + Helper(i + 2, nums);
        int skip = Helper(i + 1, nums);

        return _memo[i] = Math.Max(rob, skip);
    }
}

Editorial

Approach 1: Recursion with Memoization

class Solution:

    def __init__(self):
        self.memo = {}

    def rob(self, nums: List[int]) -> int:

        self.memo = {}

        return self.robFrom(0, nums)

    def robFrom(self, i, nums):

        # No more houses left to examine.
        if i >= len(nums):
            return 0

        # Return cached value.
        if i in self.memo:
            return self.memo[i]

        # Recursive relation evaluation to get the optimal answer.
        ans = max(
            self.robFrom(i + 1, nums), self.robFrom(i + 2, nums) + nums[i]
        )

        # Cache for future use.
        self.memo[i] = ans
        return ans

Approach 2: Dynamic Programming

class Solution:

    def rob(self, nums: List[int]) -> int:

        # Special handling for empty case.
        if not nums:
            return 0

        maxRobbedAmount = [None for _ in range(len(nums) + 1)]
        N = len(nums)

        # Base case initialization.
        maxRobbedAmount[N], maxRobbedAmount[N - 1] = 0, nums[N - 1]

        # DP table calculations.
        for i in range(N - 2, -1, -1):

            # Same as recursive solution.
            maxRobbedAmount[i] = max(
                maxRobbedAmount[i + 1], maxRobbedAmount[i + 2] + nums[i]
            )

        return maxRobbedAmount[0]