Chapter 2: The Formula Derivation Framework

Most people struggle with DP not because the code is hard, but because they try to see the formula directly from the problem statement. They stare at “minimum cost climbing stairs” and hope a recurrence magically appears. It rarely does.

What separates people who can derive DP solutions from those who can only recognize solved patterns is a systematic process. This chapter gives you that process — five steps you can apply to any DP problem, whether it is optimization or counting, 1D or 2D.

Do not hunt for the formula. Hunt for the decision at each state. The formula follows from the decision.

The 5 Steps

Every DP recurrence, no matter how complex, can be derived by answering these five questions in order. Skipping or reordering them is the main reason derivations fail.

Step 1: Define the Subproblem

Ask: “What does dp[i] (or dp[i][j]) represent?” This is the most important step. Get it wrong and everything downstream fails — your recurrence will be wrong, your base cases will be wrong, and your code will pass some tests by accident while failing others.

A good subproblem definition is:

• Specific — “minimum cost to reach step i” not “cost of stairs”
• Self-contained — the answer depends only on the parameters (i, j, etc.) and the input
• Aligned with the goal — the final answer must be expressible as some dp[...] value

Step 2: Identify the Last Decision

Ask: “What was the last choice made before reaching this state?” Work backwards from state i. How could you have arrived here? Each distinct way of arriving becomes a branch in your recurrence.

For climbing stairs with cost: you either took 1 step from i-1 (paying cost[i-1]) or 2 steps from i-2 (paying cost[i-2]). For decode ways: you either decoded the last character alone or the last two characters as a pair.

Step 3: Write the Recurrence from the Decision

Each branch of the last decision becomes a term in your formula. For optimization problems, combine with min or max. For counting problems, combine with +. The recurrence should reference only strictly smaller subproblems.

Step 4: Identify Base Cases

Ask: “What are the smallest subproblems I can solve by inspection?” These are the seeds of your table — values you set directly without applying the recurrence. Getting base cases wrong is the most common source of off-by-one errors.

Step 5: Determine Fill Order

Ask: “Which cells must be ready before I compute the current one?” Your fill order must respect these dependencies. For most 1D problems, left-to-right works. For 2D problems, you often fill row-by-row or column-by-column. Interval DP fills by increasing interval length.

Worked Example: Min Cost Climbing Stairs

Problem: Given an array cost where cost[i] is the cost of stepping on step i, find the minimum cost to reach the top. You can start at step 0 or 1, and each step you can climb 1 or 2 stairs.

Walk through all five steps below. Try to answer each prompt before revealing the answer.

With cost = [10, 15, 20]: dp[2] = min(dp[1]+cost[1], dp[0]+cost[0]) = min(15, 10) = 10, then dp[3] = min(dp[2]+cost[2], dp[1]+cost[1]) = min(30, 15) = 15. The minimum cost to reach the top is 15 — start at step 1 (free), then take one step to the top (pay cost[1] = 15).

Worked Example 2: Decode Ways

Problem: Given a string s containing digits, return the number of ways to decode it. Mapping: '1'→A, ..., '26'→Z. A string with no valid decoding returns 0.

This is a counting problem, not optimization. The recurrence uses addition instead of min/max. The tricky part is handling invalid digits — a leading '0' or pairs outside 10–26 contribute nothing.

Example: s = "226"

• 2 | 2 | 6 → B, B, F
• 2 | 26 → B, Z
• 22 | 6 → V, F

Common Pitfalls

Is It DP? Decision Checklist

Use this flowchart whenever you are unsure whether a problem is DP, greedy, or something else. Walk through each question honestly before jumping to a table.

Practice Exercises

Test your subproblem definition skills. These problems appear in later chapters — getting the definition right now will make everything else easier.