The Code From "Dynamic Programming: How to Talk Through It When You're Stuck"

Companion piece for the YouTube video. The snippets in the order they appear on screen: the top-down memoization template, then House Robber built up from a bottom-up table to O(1) space -- plus a bonus top-down version of House Robber to show the pairing the video talks about. No extra commentary here beyond what you need to read the code. The full walkthrough of the decisions behind each one, and the framework for what to say when you're stuck, is in the video.

The framework, in one place

Before any code, say these out loud:

1. Optimal substructure. "The answer for input n depends on the answers for smaller inputs in a predictable way."
2. State. What does dp[i] mean, in one sentence. If you can't finish that sentence, you're not ready to write code.
3. Recurrence. How dp[i] is built from dp[i-1], dp[i-2], dp[i][j-1], and so on.
4. Base cases. What is dp[0]? dp[1]? Empty string, empty array.

If you can't see the DP solution immediately, write the recursive brute force first. The recursion exposes the subproblems, and once you can see the subproblems you add memoization. A correct recursion with memoization is a correct DP solution.

Top-down memoization template

Start from the recursive solution, add a cache. This shape works for any linear DP problem: replace the base case and the recurrence with your problem's specifics.

def solve(n, memo=None):
    if memo is None:
        memo = {}
    if n in memo:
        return memo[n]
    if n <= 1:  # base case
        return n

    memo[n] = solve(n - 1, memo) + solve(n - 2, memo)
    return memo[n]

On screen the video uses memo={} as a default argument to keep it short. That default dict is created once and shared across calls, which is a common Python gotcha, so the version here takes memo=None and builds the dict inside. Same idea, safe to reuse.

House Robber, top-down (bonus, not on screen)

LeetCode 198. Houses in a row, each with some money, adjacent houses can't both be robbed. best(i) is the most you can rob from houses 0..i. Either you skip house i and take best(i-1), or you rob it and take best(i-2) + nums[i].

def rob(nums):
    memo = {}

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

    return best(len(nums) - 1)

This is the version to reach for under pressure. It follows the recursive structure directly, and the cache converts it to DP mechanically. Then offer the bottom-up conversion.

House Robber, bottom-up tabulation

Same recurrence, filled left to right instead of recursively. dp[i] is the maximum robbable from the first i + 1 houses.

def rob(nums):
    if not nums:
        return 0
    if len(nums) == 1:
        return nums[0]

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

    for i in range(2, len(nums)):
        dp[i] = max(dp[i - 1], dp[i - 2] + nums[i])

    return dp[-1]

O(n) time, O(n) space. No recursion, no stack depth limit.

House Robber, O(1) space

dp[i] only ever reads dp[i-1] and dp[i-2], so the full array is wasted memory. Keep two variables.

def rob(nums):
    if not nums:
        return 0
    if len(nums) == 1:
        return nums[0]

    prev2 = nums[0]
    prev1 = max(nums[0], nums[1])

    for i in range(2, len(nums)):
        current = max(prev1, prev2 + nums[i])
        prev2 = prev1
        prev1 = current

    return prev1

Mention this out loud in an interview even if you don't write it. It shows you're thinking about space, not just correctness.

Where the linear-DP pattern transfers

The "dp[i] depends on dp[i-1] and dp[i-2]" shape is the same across:

• Climbing Stairs (LeetCode 70)
• Fibonacci Number (LeetCode 509)
• Min Cost Climbing Stairs (LeetCode 746)
• House Robber II (LeetCode 213), houses in a circle, run the same pass twice: once excluding the first house, once excluding the last, take the max
• Maximum Subarray (LeetCode 53), Kadane's algorithm is linear DP with the state "best sum ending at i"

Full breakdown of the three steps before you write code, top-down versus bottom-up, the four DP patterns, and the four mistakes that cost candidates points, in the video. Next up in the series: system design, starting with the URL shortener.