How to solve a Dynamic Programming Problem ?

Dynamic Programming (DP) is about breaking a complex problem into smaller overlapping subproblems and reusing their results instead of recomputing them.

Below is a clear, repeatable framework you can apply to almost any DP problem, plus a Python example.

1️⃣ Recognize a DP Problem

A problem is suitable for DP if it has both:

✅ Overlapping Subproblems

• Same subproblems appear multiple times
• Example: Fibonacci, knapsack, shortest paths

✅ Optimal Substructure

• Optimal solution can be built from optimal solutions of subproblems
• Example: shortest path to node X uses shortest paths to previous nodes

If brute force recursion repeats work → DP is likely the answer.

2️⃣ Define the State (The Most Important Step)

Ask yourself:

What is the minimum information needed to describe a subproblem?

Examples:

• dp[i] → answer for first i elements
• dp[i][j] → answer using first i items with capacity j
• dp[i][j] → best answer for substring s[i:j]

Rule of thumb:

One DP dimension = one decision axis

3️⃣ Write the Recurrence Relation

Express how the state depends on smaller states.

General form:

dp[state] = best(
    dp[smaller_state_1],
    dp[smaller_state_2],
    ...
)

Examples:

• Fibonacci:

dp[n] = dp[n-1] + dp[n-2]

• Coin change:

dp[x] = min(dp[x - coin] + 1)

4️⃣ Identify Base Cases

Base cases stop the recursion and anchor the DP.

Examples:

dp[0] = 0
dp[1] = 1
dp[empty_string] = true

If your base cases are wrong → the entire solution fails.

5️⃣ Choose DP Style

🟦 Top-Down (Memoization)

• Recursive + cache
• Easier to write
• Good for complex states

from functools import lru_cache

@lru_cache(None)
def dp(n):
    if n <= 1:
        return n
    return dp(n - 1) + dp(n - 2)

🟩 Bottom-Up (Tabulation)

• Iterative
• Faster, no recursion
• Easier to optimize space

dp = [0, 1]
for i in range(2, n + 1):
    dp.append(dp[i - 1] + dp[i - 2])

6️⃣ Decide the Iteration Order

You must compute smaller states first.

Examples:

• 1D DP → left to right
• 2D DP on strings → increasing length
• Knapsack → careful about loop direction

Wrong iteration order = wrong answer ❌

7️⃣ Optimize Space (If Needed)

Many DP problems only need previous states.

Example: Fibonacci

a, b = 0, 1
for _ in range(n):
    a, b = b, a + b

Space drops from O(n) → O(1).

8️⃣ Worked Example: Climbing Stairs

Problem

You can climb n stairs, taking 1 or 2 steps at a time. How many distinct ways?

Step-by-step

State

dp[i] = number of ways to reach step i

Recurrence

dp[i] = dp[i-1] + dp[i-2]

Base cases

dp[0] = 1
dp[1] = 1

Python solution

def climb_stairs(n: int) -> int:
    if n <= 1:
        return 1

    dp = [0] * (n + 1)
    dp[0] = dp[1] = 1

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

    return dp[n]

9️⃣ Common DP Patterns (Learn These!)

10️⃣ Mental Checklist (Use This Every Time)

✔ What is my state? ✔ What is the transition? ✔ What are the base cases? ✔ What is the order of computation? ✔ Can I optimize space?