Dynamic Programming Explained: A Beginner-Friendly Method with Examples

What dynamic programming is

Dynamic programming (DP) is a way of solving a problem by breaking it into smaller overlapping subproblems, solving each subproblem once, and storing the answer so it is never recomputed. It turns slow exponential solutions into fast polynomial ones. DP is a favourite in product-company interviews, so it deserves patient practice (DSA study plan).

When to suspect DP

A problem is a DP candidate when:

1. Optimal substructure: the best answer is built from best answers to smaller versions of the problem
2. Overlapping subproblems: a plain recursive solution solves the same subproblem again and again
3. The question asks for a count, minimum, maximum or yes/no over many choices ("how many ways", "minimum cost", "is it possible")

The four-step method

1. Define the state: what does dp[i] (or dp[i][j]) mean? Say it in a sentence.
2. Write the transition: how does a state depend on smaller states?
3. Set the base cases: the smallest states with known answers
4. Choose the order and the answer: fill in an order where dependencies are ready, and decide which cell holds the final answer

Two ways to implement it:

• Top-down (memoisation): write the recursion, then cache results
• Bottom-up (tabulation): fill a table iteratively; usually faster and easier to optimise for space

Example 1: Fibonacci

Plain recursion fib(n) = fib(n-1) + fib(n-2) repeats work and takes exponential time. With memoisation:

def fib(n, memo={}):
    if n <= 1:
        return n
    if n not in memo:
        memo[n] = fib(n - 1, memo) + fib(n - 2, memo)
    return memo[n]

Time O(n). Bottom-up needs only two variables, so space is O(1).

Example 2: climbing stairs

You can climb 1 or 2 steps at a time. How many ways to reach step n?

• State: dp[i] = number of ways to reach step i
• Transition: dp[i] = dp[i-1] + dp[i-2]
• Base: dp[0] = 1, dp[1] = 1

It is the same as Fibonacci in disguise, which is common: many problems reduce to a familiar pattern.

Example 3: coin change (minimum coins)

Given coin values and a target amount, find the fewest coins.

def coin_change(coins, amount):
    INF = amount + 1
    dp = [0] + [INF] * amount          # dp[a] = fewest coins to make amount a
    for a in range(1, amount + 1):
        for c in coins:
            if c <= a:
                dp[a] = min(dp[a], dp[a - c] + 1)
    return dp[amount] if dp[amount] != INF else -1

Time O(amount × number of coins). A greedy approach (always take the largest coin) can fail for some coin sets, which is why DP is needed.

Example 4: 0/1 knapsack

Each item has a weight and a value; choose items to maximise value within a weight limit, using each item at most once.

• State: dp[i][w] = best value using the first i items with capacity w
• Transition: either skip the item, or take it if it fits: dp[i][w] = max(dp[i-1][w], value[i] + dp[i-1][w - weight[i]])

def knapsack(weights, values, cap):
    dp = [0] * (cap + 1)
    for wt, val in zip(weights, values):
        for w in range(cap, wt - 1, -1):     # go backwards so each item is used once
            dp[w] = max(dp[w], val + dp[w - wt])
    return dp[cap]

Example 5: longest common subsequence (LCS)

For strings a and b, dp[i][j] is the LCS length of the first i characters of a and the first j of b.

• If a[i-1] == b[j-1]: dp[i][j] = dp[i-1][j-1] + 1
• Otherwise: dp[i][j] = max(dp[i-1][j], dp[i][j-1])

This pattern leads to edit distance, longest palindromic subsequence and many string problems.

Common DP families to practise

• 1D linear: climbing stairs, house robber, maximum subarray
• Grid paths: unique paths, minimum path sum
• Subsequences and strings: LCS, longest increasing subsequence, edit distance
• Knapsack style: subset sum, partition equal subset, coin change, target sum
• Intervals and partitions: matrix chain, palindrome partitioning
• Others: DP on trees, bitmask DP and DP with states for stock-buying problems

Common mistakes

• Starting to code before defining the state in words
• Wrong base cases or wrong iteration order
• Forgetting that a variant (each item once vs unlimited) changes the loop direction
• Memorising solutions instead of understanding the pattern

A practice routine

1. Solve 5 problems from each family above, writing the state and transition before any code
2. Solve each twice: recursion with memoisation first, then the table
3. Revisit them after a week without looking at solutions
4. Learn space optimisation (keep only the previous row) after the basic version works

Combine this with pattern-based practice plan and the online coding assessment tips of clarifying, planning aloud, coding and testing.