# Dynamic Programming

Solving problems by combining solutions to overlapping subproblems, storing each result once instead of recomputing it.

**Rests on:** Memoization, Recursive Thinking

**Leads to:** Merge Sort and Quicksort

*Machine Learning · Algorithms and Complexity*


## Why learn this

You face decisions daily that require choosing the best path among many possibilities, whether scheduling projects, allocating resources, or optimizing logistics. Solving these by guessing or trying every combination is slow and error-prone. Dynamic programming is a method for solving these problems efficiently by reusing previous answers instead of starting from scratch each time. For example, when an app finds the fastest route home, it does not re-examine every possible street corner; it reuses the best partial routes it already calculated. Without this approach, tasks like matching genetic sequences or transcribing speech would take years on modern computers. Mastering this concept explains why some systems feel instantaneous while others lag, and it provides the foundation for understanding more advanced automation techniques.


## The intuition

Imagine you run a small delivery service and need to find the cheapest way to travel between two cities. You have a map of roads, each with a specific toll cost. One approach is to try every possible route and sum up the costs. This works for a tiny map, but if you have 20 cities, the number of routes explodes into millions, making it practically impossible to check them all manually.

Now, notice a structural truth: if the cheapest route from City A to City B goes through City C, then the segment from City A to City C must also be the cheapest way to get from A to C. If there were a cheaper path from A to C, you could swap it in and make the whole trip cheaper, which contradicts the assumption that your original route was cheapest.

This means you can break the big problem (A to B) into smaller pieces. The key insight is that many of these pieces are identical. For instance, finding the cheapest path from City X to City Y might be a sub-step for reaching City Z, City W, and City V. Instead of calculating the cost from X to Y three separate times, you calculate it once, write it down on a notepad (a table), and look it up whenever another route needs that segment. This is dynamic programming: break a large problem into smaller overlapping parts, solve each unique part once, save the answer, and use those saved answers to build the final solution.


## An analogy

Think of planning a dinner party where several dishes share ingredients. You need chopped onions, diced tomatoes, and grated cheese for multiple recipes. If you followed each recipe as a completely separate project, you would chop an onion, then chop another onion later for the next dish, wasting time and effort.

Dynamic programming is like preparing all ingredients first: you chop the onions once, put them in a bowl, and add the bowl to your shopping list of prepped items. Whenever any recipe calls for onions, you grab from that single bowl instead of chopping again. You are trading a bit of counter space (memory) for a lot of cooking time.

This works because the need for 'chopped onions' appears in multiple places. If every dish required a completely unique ingredient, you wouldn't need to pre-chop; you could just handle each task as it came up. Similarly, in problem-solving, this method only helps when the same small calculation is needed by different larger calculations.


## Definition

Dynamic programming is a technique for solving complex problems by dividing them into smaller, repeating sub-problems, solving each distinct sub-problem exactly once, storing its result for future use, and combining those stored results to reach the final answer.


## How it connects

Dynamic programming is a core strategy within computer science algorithms. It is closely related to Divide and Conquer; both break problems down, but Divide and Conquer splits a problem into independent parts that are solved separately, whereas Dynamic Programming handles parts that overlap and share information. It is also fundamental to understanding Big-O notation, specifically how we describe how long an algorithm takes; dynamic programming often changes the description of time required from growing exponentially (impossible for large inputs) to growing polynomially (manageable). Finally, it illustrates the space-time tradeoff, where you accept using more storage to save calculation time.


## The mathematics

Dynamic programming is a method for solving complex problems by breaking them down into simpler, overlapping subproblems. The key insight is that you do not need to solve the same small problem twice. Instead, you solve each small problem once, write the answer down in a table (often called a memo or a DP table), and look up that answer whenever you need it again.

To use dynamic programming, you must define two things: the state and the recurrence relation.

1. The State: This is a description of a specific subproblem. It is defined by one or more numbers (variables) that tell you exactly which part of the big problem you are looking at. For example, if you are counting ways to climb stairs, the state is simply the number of steps remaining. If you are finding the shortest path in a grid, the state might be your current row and column position.

2. The Recurrence Relation: This is the rule that tells you how to calculate the answer for a larger state using the answers for smaller states. It expresses the value of the current state as a function of previous states.

3. Base Cases: These are the smallest, simplest subproblems whose answers are known immediately without any calculation. They stop the recursion from going on forever.

The algorithm works by filling out a table. You start with the base cases (the smallest states) and fill in the table step-by-step until you reach the state that represents your original, big problem. The value in that final cell is your answer.

Let us look at the general structure using plain language instead of code symbols:

- Let `Answer(n)` be the function that gives the result for a problem of size `n`.
- The recurrence says: `Answer(n) = Answer(n - 1) + Answer(n - 2)`.
- This means: To find the answer for size `n`, take the answer for size `n-1` and add it to the answer for size `n-2`.
- The base cases are:
  - `Answer(0) = 1`
  - `Answer(1) = 1`

You do not need algebra to understand this. You just need to follow the rule: "To get the next number, add the two numbers before it." This is exactly how the Fibonacci sequence is built.

Why is this better than solving it by hand or with simple recursion? Because in a naive recursive approach, to find `Answer(4)`, you would calculate `Answer(3)` and `Answer(2)`. To find `Answer(3)`, you would calculate `Answer(2)` and `Answer(1)`. Notice that `Answer(2)` is calculated twice. As the problem gets bigger, this duplication grows exponentially. Dynamic programming avoids this by storing the result of `Answer(2)` the first time it is computed and reusing it the second time.


## A worked example

Let us solve a concrete example: Climbing a Staircase.

Problem Statement:
You are at the bottom of a staircase with 4 steps. You can climb either 1 step or 2 steps at a time. How many distinct ways are there to reach the top (step 4)?

Step 1: Define the State and Base Cases
Let `Ways(n)` be the number of distinct ways to reach step `n`.
- If you are already at step 0 (the ground), there is exactly 1 way to be there: do nothing. So, `Ways(0) = 1`.
- If you are at step 1, there is only 1 way to get there: take one 1-step from the ground. So, `Ways(1) = 1`.

Step 2: Define the Recurrence Relation
To reach step `n`, your last move must have been either:
- A 1-step from step `n-1`.
- A 2-step from step `n-2`.
Therefore, the total number of ways to reach step `n` is the sum of the ways to reach step `n-1` and the ways to reach step `n-2`.
Formula: `Ways(n) = Ways(n-1) + Ways(n-2)`

Step 3: Fill the Table (Bottom-Up)
We start from the base cases and work our way up to `n=4`.

- For n = 0:
  `Ways(0) = 1` (Base case)

- For n = 1:
  `Ways(1) = 1` (Base case)

- For n = 2:
  We use the formula: `Ways(2) = Ways(1) + Ways(0)`
  Substitute the known values: `Ways(2) = 1 + 1`
  Result: `Ways(2) = 2`
  (The two ways are: 1-step then 1-step, or one 2-step.)

- For n = 3:
  We use the formula: `Ways(3) = Ways(2) + Ways(1)`
  Substitute the known values: `Ways(3) = 2 + 1`
  Result: `Ways(3) = 3`
  (The three ways are: 1-1-1, 1-2, or 2-1.)

- For n = 4:
  We use the formula: `Ways(4) = Ways(3) + Ways(2)`
  Substitute the known values: `Ways(4) = 3 + 2`
  Result: `Ways(4) = 5`

Final Answer:
There are 5 distinct ways to climb a staircase of 4 steps.

Comparison with Naive Recursion:
If we had calculated this without storing previous results (naive recursion):
- To find `Ways(4)`, we need `Ways(3)` and `Ways(2)`.
- To find `Ways(3)`, we need `Ways(2)` and `Ways(1)`.
- Here, `Ways(2)` is needed twice. If we went to `n=5`, `Ways(3)` would be needed twice, and `Ways(2)` three times. The work grows very fast. Dynamic programming ensures each `Ways(n)` is calculated exactly once.


## From scratch, in Python

```python
def fib(n):
    if n <= 1:
        return n
    return fib(n-1) + fib(n-2)

# Dynamic programming: bottom-up tabulation
def fib_dp(n):
    if n <= 1:
        return n
    dp = [0] * (n + 1)  # a list to store results for 0..n
    dp[0] = 0
    dp[1] = 1
    for i in range(2, n + 1):
        dp[i] = dp[i-1] + dp[i-2]  # accessing stored values
    return dp[n]

print(fib_dp(10))  # 55
```


## What the code does

This code calculates the nth Fibonacci number. The first function `fib` is a naive recursive version, which recomputes the same values many times, causing exponential blowup. The second function `fib_dp` is the dynamic programming version. We create a list `dp` of length `n+1`. A list is like a row of boxes, each holding a number, and we refer to them by their position, starting at 0. So `dp[0]` is the first box, `dp[1]` the second, and so on. We set the base cases `dp[0] = 0` and `dp[1] = 1`. Then we loop over `i` from 2 to `n` (using `range`), and for each `i`, we set `dp[i]` to the sum of the two previous values, `dp[i-1]` and `dp[i-2]`, which are already computed. Finally, we return `dp[n]`. The key is that every value is computed exactly once, so the time grows linearly with `n` instead of exponentially.


## Common misconceptions

**DP is only for optimization problems** — Dynamic programming is only for finding the best or cheapest option.

Many DP problems are counting problems (like the staircase example) or probability calculations, not just optimizations. In fact: Dynamic programming applies to any problem with overlapping subproblems and optimal substructure, whether you're counting, optimizing, or computing probabilities.

**Greedy and DP are the same** — A greedy algorithm and dynamic programming both make local choices, so they're basically the same.

Greedy makes a single irreversible choice that seems best at the moment, without considering future implications. DP evaluates all possible choices by combining solutions to subproblems. In fact: Greedy is a shortcut that works only for problems with a special structure; DP is more general and always considers the full space of possibilities, but requires more computation.

**DP always needs a table of all results** — You must store every subproblem's result in a big table.

Some DP problems can be solved with just the last few results, as in the Fibonacci case. You can use a rolling array or even just two variables. In fact: You only need to store results that will be used later. If a result is never referenced again, you can discard it.

**DP is a specific algorithm** — Dynamic programming is a specific algorithm like binary search.

DP is a general design technique. There is no single DP algorithm; there are countless DP algorithms for different problems. In fact: Dynamic programming is a way of thinking about problems, not a recipe. You design the state and recurrence for each problem.

**Memoization and DP are different things** — Memoization is a trick, not related to DP.

Memoization is simply top-down dynamic programming. It caches function results before they're recomputed. The difference is in the order of computation, but the idea is identical. In fact: Memoization is a top-down implementation of dynamic programming. You can implement the same recurrence bottom-up or top-down, and both are considered DP.


## In short

Dynamic programming is a method for solving complex problems by breaking them into overlapping subproblems, solving each once, storing the results, and combining them. The key is to identify the state (the variables that define a subproblem) and find a recurrence. You then fill in a table bottom-up (or use memoization top-down). It's used everywhere in AI, from sequence alignment to reinforcement learning, and it's the difference between exponential and polynomial time. Remember: the art is in choosing the right state definition.


## Where this is used

Dynamic programming appears everywhere in AI. In large language models (LLMs) like ChatGPT, it's used for efficient tokenization: the model splits text into pieces (subword tokens) using dynamic programming to find the optimal segmentation that maximizes the likelihood of the observed text. In speech recognition, the Viterbi algorithm, which is a form of dynamic programming, finds the most likely sequence of words given the audio signal, efficiently combining probabilities across time steps. In reinforcement learning — the field behind AlphaGo and robotics — the value function is computed using a dynamic programming approach, typically through the Bellman equations, which are a recurrence relationship similar to what you've seen. This is how an agent learns which actions lead to the highest long-term reward, by storing the value of each state and updating it iteratively. For small models running on devices, dynamic programming is used in algorithms that find the optimal order of operations for matrix multiplication, saving memory and energy. In retrieval-augmented generation (RAG), dynamic programming can be used for efficient search over knowledge bases, finding the best sequence of documents to answer a query. In agentic systems that plan and call tools, dynamic programming appears in planning algorithms that compute optimal action sequences given a model of the environment. In everyday applied machine learning, dynamic programming is used in sequence alignment for DNA analysis, in time-series forecasting (e.g., dynamic time warping to align sequences), and in recommendation systems that optimise over user-item interactions. For a developer, these algorithms are often implemented in libraries like `numpy` (e.g., `np.fft` uses clever divide-and-conquer, but for DP, you'd use libraries like `numba` for speed or custom loops). The biggest risk in implementing DP badly is using exponential time accidentally by forgetting to store results, or overflowing your storage table with unnecessary memory. A good developer checks the state space size before building the table, and uses iterative bottom-up versions instead of recursive ones when the recursion stack might overflow.


---

Read this on the web: https://basavapurushottam.com/learn-ai/dynamic-programming
