Dynamic Programming — How to Define the State, Three Walkthroughs

Dynamic programming isn't a technique — it's a habit of asking "what would I need to know to solve a smaller version of this problem?" Naming that "what would I need to know" is 90% of the work; the recurrence and code follow mechanically. This post is the pattern-recognition guide to the naming step: how to define the state, how to know when the state is right, and how the same three-part shape solves three canonical DP problems.

Recognition — when to reach for it

DP is the right tool when all three of these hold:

The problem asks for an optimum — max, min, count, or existence — over decisions you make one step at a time.
The naïve recursion has overlapping subproblems — the same "what's the best sub-answer starting from state X?" gets asked many times.
The state space is polynomial in the input, or at least tractable.

If the recursion has overlapping subproblems but the state space is exponential (LC 51 N-Queens), you want backtracking with pruning, not DP. If the state space is polynomial but decisions don't compound (each choice is independent), a greedy or scan may beat DP.

The three-part shape

Every DP solution answers three questions in order:

State. What information about the current subproblem uniquely identifies it? Usually one or two integers — an index into the input, a remaining budget, a "did we already do X?" boolean. Common shapes: dp[i], dp[i][j], dp[i][remaining].
Transition. For each state, what smaller states does it depend on, and how do we combine them? "Take, or don't take" is the classic two-branch transition. "Try every prefix / every partition" is the classic n-branch transition.
Base case. The state that's the trivial answer — usually "no items left" or "index 0". Every recursion has to bottom out somewhere.

Get the state right and the transition and base case fall out mechanically. Get the state wrong — miss a dimension or add a redundant one — and no amount of clever transition writing will save you.

The most common state shapes

dp[i]: "answer for the first i items" or "answer starting at index i". LC 198 House Robber, LC 70 Climbing Stairs, LC 300 Longest Increasing Subsequence (variant).
dp[i][j]: "answer for the range [i, j]" or "answer for i of A matched against j of B". LC 1143 Longest Common Subsequence, LC 72 Edit Distance, LC 5 Longest Palindromic Substring (interval DP).
dp[i][remaining]: "answer considering the first i items with remaining budget left". LC 322 Coin Change, LC 494 Target Sum, LC 416 Partition Equal Subset Sum.
dp[mask]: "answer over the subset represented by mask". LC 847 Shortest Path Visiting All Nodes — bitmask DP for small n.
dp[i][k]: "answer for the first i items with exactly k of some resource used". LC 188 Best Time to Buy and Sell Stock IV, LC 123 (k = 2 fixed).

Naming the state precisely — and admitting when a dimension is missing — is the interview-visible skill DP tests.

Walkthrough 1 — LeetCode 198, House Robber

You cannot rob two adjacent houses. Given an array of house values, return the maximum you can rob.

State. dp[i] = maximum you can rob from houses 0..i. One dimension because the only thing that matters at index i is the best you've done so far — not which houses you took.

Transition. At house i, two choices: take it (adding nums[i] + dp[i - 2]) or skip it (dp[i - 1]). Max the two.

Base case. dp[0] = nums[0], dp[1] = max(nums[0], nums[1]).

def rob(nums: list[int]) -> int:
    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]

Only the previous two values matter — the rolling-variable optimisation collapses this to O(1) space:

def rob(nums: list[int]) -> int:
    prev2, prev1 = 0, 0
    for x in nums:
        prev1, prev2 = max(prev1, prev2 + x), prev1
    return prev1

Same algorithm, O(n) time, O(1) space. This is the "rolling array" optimisation described in the space complexity post — the recurrence only reads the last two values, so keep only those two.

Walkthrough 2 — LeetCode 300, Longest Increasing Subsequence

Given an array, return the length of the longest strictly increasing subsequence.

State — first attempt. dp[i] = "LIS ending at index i". Note the key word ending. This is what makes the state well-defined: without it, "LIS considering the first i items" isn't enough to know whether extending is legal, because we don't know what the last element was.

Transition. dp[i] = 1 + max(dp[j] for j < i if nums[j] < nums[i]). If no j qualifies, dp[i] = 1 (the subsequence is just nums[i] by itself).

Base case. dp[i] = 1 for every i, before considering earlier indices.

def lengthOfLIS(nums: list[int]) -> int:
    n = len(nums)
    dp = [1] * n
    for i in range(n):
        for j in range(i):
            if nums[j] < nums[i]:
                dp[i] = max(dp[i], dp[j] + 1)
    return max(dp)

O(n²) time, O(n) space. Answer is max(dp), not dp[-1] — the longest increasing subsequence can end at any index, not necessarily the last.

The O(n log n) variant reshapes the state entirely. Maintain a tails array where tails[k] is the smallest possible tail of a length-k + 1 increasing subsequence seen so far. For each x, bisect_left gives the position where x extends or replaces. Length of the LIS is len(tails).

from bisect import bisect_left

def lengthOfLIS(nums: list[int]) -> int:
    tails = []
    for x in nums:
        i = bisect_left(tails, x)
        if i == len(tails):
            tails.append(x)
        else:
            tails[i] = x
    return len(tails)

O(n log n) time, O(n) space. The state definition is completely different — no dp[i]; instead the state is the tails array. Same problem, two DPs of different shapes. Recognising when to reshape the state is the deeper interview skill.

Walkthrough 3 — LeetCode 322, Coin Change

Given denominations and an amount, return the fewest number of coins to make amount, or -1 if impossible.

State. dp[a] = fewest coins to make amount a. One dimension because the only thing that matters at amount a is how many coins to reach it — not which coins.

Transition. dp[a] = min(dp[a - c] + 1 for c in coins if c ≤ a). If no c qualifies (or all dp[a - c] are infinity), dp[a] stays infinity.

Base case. dp[0] = 0 — zero coins to make amount 0.

def coinChange(coins: list[int], amount: int) -> int:
    dp = [float('inf')] * (amount + 1)
    dp[0] = 0
    for a in range(1, amount + 1):
        for c in coins:
            if c <= a and dp[a - c] + 1 < dp[a]:
                dp[a] = dp[a - c] + 1
    return dp[amount] if dp[amount] != float('inf') else -1

O(amount × len(coins)) time, O(amount) space. This is bottom-up (tabulation); the top-down (memoisation) version reads even more like the recursion — see the DP memoisation vs tabulation post for the decision.

The state definition worth noticing: dp[a] does not depend on i, the coin index. Because coins can be reused, we don't need to track "which coins we've considered so far". Coin Change II (LC 518, count-of-ways variant) does need that dimension — the recurrence there is dp[i][a], and dropping the i gives wrong answers because it over-counts orderings.

Getting the state right

Three diagnostic questions when the state doesn't feel right:

"If I gave you the state, could you produce the same answer regardless of history?" If two paths reach the same state but need different answers, the state is missing a dimension.
"If I gave you the state, does the transition read as an obvious recurrence?" If you find yourself asking "wait, but I need to know if we already X" while writing the transition, that "X" is the missing dimension.
"Does the state have any dimension I'm not actually using in the transition?" Extra dimensions inflate memory and time by a factor of that dimension's size. Drop them.

The gap between "correct DP" and "elegant DP" is usually one dimension in the state.

When DP is not the tool

Greedy works. LC 55 Jump Game has a linear greedy solution; DPing it is O(n²) or O(n) with more work than needed. Try greedy first when choices are independent.
The state space is exponential. N-Queens has 2ⁿ subsets to consider; DP tables of that size are impractical past n ≈ 20. Bitmask DP (LC 847) works up to n ≈ 20; beyond that, backtracking.
The problem is single-source shortest path with weighted edges. Dijkstra's, not DP.
The answer only needs a running property, not future planning. LC 121 Best Time to Buy and Sell Stock is a linear scan with a running min. DPing it is over-engineering.

How the Algotrek tutor would prompt you here

When a learner opens a DP problem on Algotrek, the tutor doesn't reveal the recurrence. It asks three questions:

"What information about the current subproblem uniquely identifies it?" — Forces the state to be named. Getting this right is 90% of DP; the rest is arithmetic.
"Given the state, what smaller states does it depend on?" — This is the transition. Two branches (take/don't take), n branches (try every partition), or one branch chained (LCS-style).
"What's the smallest state whose answer you know directly?" — Base case. Almost always "empty prefix" or "amount 0".

Answer all three and the DP writes itself. Miss any one and you'll re-derive the wrong solution three times before noticing.

Where to go next

LC 1143, Longest Common Subsequence. The canonical dp[i][j] interval DP. Once you own it, LC 72 Edit Distance and LC 583 Delete Operation for Two Strings are variations.
LC 416, Partition Equal Subset Sum. Subset-sum DP — the "did we already reach sum s using first i items?" recurrence. Bridges knapsack.
LC 5, Longest Palindromic Substring. Interval DP with a palindromic invariant. Alternative solutions (expand-around-centre, Manacher's) make it a nice study in state-choice trade-offs.
LC 494, Target Sum. Reduces to subset-sum after a clever transformation. Recognising this reduction is the graduation exercise.
LC 188, Best Time to Buy and Sell Stock IV. The dp[i][k][holding] shape — one more dimension than most DPs. Getting comfortable with three dimensions is the interview-hard-tier skill.

Cross-reference the DP memoisation vs tabulation post for the top-down vs bottom-up decision once you've defined the state. Cross-reference the space complexity post for the rolling-array optimisation that drops most DPs from O(n × m) space to O(m).

For the O(states × transition_cost) accounting that every DP uses, see the Big-O cheat sheet. For the Python-specific @cache and float('inf') idioms the code above uses, see the Python interview cheat sheet.