Introduction

Converting a top-down dynamic programming solution into a bottom-up one is mostly an exercise in understanding dependencies. A memoized recursive function already tells you which subproblems each state needs. Bottom-up DP simply computes those same states in an order where every dependency is already available. Once you see the recurrence as a dependency graph, the conversion becomes mechanical.

Start by reading the top-down state and recurrence

Suppose you have this top-down solution for the minimum number of coins needed to make a target amount:

1from functools import lru_cache
2
3
4def min_coins_top_down(coins: list[int], amount: int) -> int:
5    @lru_cache(maxsize=None)
6    def solve(remaining: int) -> int:
7        if remaining == 0:
8            return 0
9        if remaining < 0:
10            return float("inf")
11
12        best = float("inf")
13        for coin in coins:
14            best = min(best, 1 + solve(remaining - coin))
15        return best
16
17    answer = solve(amount)
18    return -1 if answer == float("inf") else answer

The state is remaining. The transition says: to compute solve(remaining), you need answers for smaller amounts such as remaining - coin.

That already tells you the bottom-up order: compute from 0 upward.

Translate base cases into table initialization

Top-down base cases become initial table values in bottom-up DP.

In the example above:

• 'solve(0) = 0 becomes dp[0] = 0'
• impossible states start as infinity

Then you fill the table in increasing amount order, because every dp[current - coin] refers to a smaller amount that should already be computed.

1def min_coins_bottom_up(coins: list[int], amount: int) -> int:
2    dp = [float("inf")] * (amount + 1)
3    dp[0] = 0
4
5    for current in range(1, amount + 1):
6        for coin in coins:
7            if current - coin >= 0:
8                dp[current] = min(dp[current], 1 + dp[current - coin])
9
10    return -1 if dp[amount] == float("inf") else dp[amount]

That is the same recurrence, just evaluated in a loop instead of through recursion.

A reliable conversion recipe

For many problems, you can convert top-down to bottom-up with the same checklist:

1. identify the DP state parameters
2. write down the recurrence plainly
3. find which states each state depends on
4. choose a loop order where those dependencies are computed first
5. translate base cases into initial table values

If the top-down state has two parameters, such as dp(i, j), the bottom-up version usually becomes a 2D table with nested loops. The challenge is deciding which dimension should go forward, backward, or both.

Dependency order is the real skill

The hardest part is not syntax. It is dependency direction.

For example:

• if dp[i] depends on dp[i - 1], loop upward
• if dp[i] depends on dp[i + 1], loop downward
• if dp[i][j] depends on dp[i - 1][j] and dp[i][j - 1], loop forward on both axes

This is why converting DP is easier when you sketch a small dependency graph by hand. The loops then almost write themselves.

Bottom-up can enable space optimization

Once the table order is explicit, you can often see that only a small part of the table is needed at any time. That is harder to notice in top-down recursion.

For example, Fibonacci or climbing-stairs problems often depend only on the previous one or two states, so a full array can collapse to a few variables:

1def fib_bottom_up(n: int) -> int:
2    if n <= 1:
3        return n
4
5    prev2 = 0
6    prev1 = 1
7
8    for _ in range(2, n + 1):
9        prev2, prev1 = prev1, prev1 + prev2
10
11    return prev1

That kind of optimization usually appears only after you already understand the bottom-up order.

Common Pitfalls

The most common mistake is copying the recurrence correctly but choosing the wrong loop order. If dependencies are not computed yet, the table fills with wrong values very quickly.

Another issue is forgetting to translate top-down base cases into bottom-up initialization. A good recurrence with bad initial values still fails.

Developers also preserve unreachable-state logic poorly. If the top-down code used float("inf"), None, or -1 as a sentinel, the bottom-up table needs an equivalent representation.

Finally, do not convert blindly. Some problems are easier to reason about top-down first. The top-down version is often the tool that reveals the correct state space.

Summary

• Bottom-up DP is the same recurrence as top-down DP evaluated in dependency order.
• Base cases become initial table values.
• The loop order comes directly from which smaller states each state depends on.
• Converting to bottom-up often makes space optimization easier to see.
• When in doubt, sketch the dependency graph before writing loops.