Description

Top-down DP = recursion + a cache. Break the problem into subproblems, solve them recursively, and memoize each answer so a subproblem is only computed once.
?

Reach for when

You have overlapping subproblems you can write as a recurrence. Use it when either only some states are actually needed (sparse), or the recursion is easier to express than working out a fill order.

Runtime

O(n)

Visualization

Pseudocode

dp(state):
	if state is a base case:
		return base value
	if state in memo:
		return memo[state]

	best = worst value              # +inf to minimize, -inf to maximize
	for each choice from state:
		best = better(best, dp(next state))

	return best

Code

from functools import cache

@cache
def dp(state):
    if is_base(state):               # base case → known answer
        return base_value(state)

    best = WORST                     # +inf to minimize, -inf to maximize
    for option in options(state):    # each choice available from this state
        best = better(best, dp(next_state(state, option)))
    return best                      # @cache memoizes automatically