LC 0198 [E] House Robber - ALawliet/algorithms GitHub Wiki

https://leetcode.com/problems/house-robber/discuss/156523/From-good-to-great.-How-to-approach-most-of-DP-problems

f(0) = nums[0]
f(1) = max(num[0], num[1])
f(i) = max(f(i-2) + nums[i], f(i-1))

class Solution:
    def rob(self, nums: List[int]) -> int:
        @cache
        def dp(i):
            if i < 0: return 0
            return max(dp(i-2) + nums[i], dp(i-1))

        return dp(len(nums)-1)

class Solution:
    def rob(self, nums: List[int]) -> int:
        memo = {}

        def dp(i):
            if i in memo:
                return memo[i]
            
            if i < 0:
                return 0
            
            choice = max(dp(i-2) + nums[i], dp(i-1))
            memo[i] = choice
            return choice
            
        return dp(len(nums)-1)

class Solution:
    def rob(self, nums: List[int]) -> int:
        if not nums: return 0
        if len(nums) == 1: return nums[0]
        
        T = [0] * len(nums)
        
        T[0] = nums[0]
        T[1] = max(nums[0], nums[1])
        
        for i in range(2, len(nums)):
            T[i] = max(T[i-2] + nums[i], T[i-1])
            
        return T[-1]

class Solution:
    def rob(self, nums):
        i1, i2 = 0, 0 # [i-1], [i-2]
        for num in nums:
            i1, i2 = i2, max(i1 + num, i2)
        return i2

/* the order is: prev2, prev1, num  */
public int rob(int[] nums) {
    if (nums.length == 0) return 0;
    int prev1 = 0;
    int prev2 = 0;
    for (int num : nums) {
        int tmp = prev1;
        prev1 = Math.max(prev2 + num, prev1);
        prev2 = tmp;
    }
    return prev1;
}