Dynamic Programming

Recursion

Forward Recursion

I saw a common pattern where thinking forwardly is easier to reason. For example, the House Robber problem:

from functools import cache

def rob(self, nums: List[int]) -> int:
    n = len(nums)
    @cache
    def dp(i: int) -> int:
        if i >= n: return 0
        return max(
            nums[i] + dp(i+2),  # rob the current house, skip the next one
            dp(i+1)             # skip the current house, rob the next one
        )

    return dp(0)

The logic is simple: at the ith house, we either: (1) rob it and move to the next next house (i+2), or (2) we don’t rob and move to the next one. When we go over the nth house, we rob nothing (0) since there is no more house to rob.

This problem also has the similar approach:

from functools import cache

def maximumScore(self, nums: List[int], multipliers: List[int]) -> int:
    n, m = len(nums), len(multipliers)
    @cache
    def dp(i, left):
        # inclusive [left, right] of nums
        if i >= m: return 0
        right = n - 1 - (i - left)
        return max(
            nums[left] * multipliers[i] + dp(i+1, left+1),
            nums[right] * multipliers[i] + dp(i+1, left)
        )
    return dp(0, 0)

Backward Recursion

Or backtracking.
Noticeably, we need to define the base case.

Background

Strategies

1. Finding state variables

2. Defining the recusion relation

Simplify the basecase.
ALWAYS VERIFY THE BASE CASE.

3. Finalizing the top-down approach

Using Python, if the recusion relation is found, then it is pretty much done with top-down approach (via cache in functools).

4. Selecting data structures for memorization

5. Finding the computation path

6. Finalizing the bottom-up approach

Other optimizations

Optimized Bottom-Up DP

Monotonic Stacks

Minimum Difficulty of a Job Schedule

Problems

Patterns

Problems

Reading

Leetcode’s Dynamic Programming: a great place to start practice DP.

Codeforces contains many insightful tutorials on DP:

Series from rembocoder is worth checking out: