from typing import List


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

    # 子问题：
    # f(k) = 偷 [0..k) 房间中的最大金额

    # f(0) = 0
    # f(1) = nums[0]
    # f(k) = max{ rob(k-1), nums[k-1] + rob(k-2) }

    N = len(nums)
    dp = [0] * (N + 1)
    dp[0] = 0
    dp[1] = nums[0]
    for k in range(2, N + 1):
        dp[k] = max(dp[k - 1], nums[k - 1] + dp[k - 2])
    return dp[N]
