Dynamic Programming: Bottom-Up (Tabulation, Knapsack)

Dynamic Programming: Bottom-Up (Tabulation, Knapsack) | Algoryva

Intuition

Climbing the stairs from the bottom

Top-down DP is like asking “what is the answer for step 100?” and letting that question trigger smaller questions. Bottom-up DP is like climbing from step 0: you know step 0, so compute step 1; you know steps 0 and 1, so compute step 2; and so on, until you reach the step you wanted.

Nothing is ever asked twice and nothing is ever *waiting* on a deeper call. You only need to be sure that when you compute a step, the steps it depends on are already written down. That ordering is the whole craft.

First, the naive way

Recursion that memoizes, but still recurses

Memoization fixes the repeated work, as you saw. But the recursion itself is still there. Each unfinished call sits on the call stack, and Python allows only about 1,000 nested calls.

So a memoized function that needs a state depth of 5,000 crashes, even though only 5,000 distinct states exist and the answer is easy to compute. The depth is a limit of the *method*, not the problem.

python

from functools import lru_cache

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

print(fib(500) > 10**100)   # True
try:
    fib(5000)
except RecursionError:
    print("recursion limit hit")   # recursion limit hit

Cost: Correct and O(n), but the stack depth equals the number of states, so a deep recursion raises RecursionError in Python.

The observation

If you know the order, you do not need the recursion

In every DP, each state depends on a few smaller states (smaller amount, fewer items, shorter prefix). That gives a natural order: fill states from smallest to largest, and every dependency is ready when you need it.

So replace the recursive calls with a loop over states in that order, and the memo dictionary with an array (a table). The recurrence is identical; only the traversal changes: top-down discovers states on demand, bottom-up computes them all in a planned order.

The concept

The tabulation recipe, and top-down versus bottom-up

Use the same state and transition as in Top-Down DP, then add three decisions:

Table: an array (1D) or list of lists (2D) with one cell per state, holding the answer for that state.
Base cells: fill the cells whose answers are known without any transition (dp[0] = 0, first row, first column).
Order: loop so that every cell is computed after the cells it reads. Usually increasing index; for some knapsack variants, decreasing (see below).
Answer cell: usually the last cell (dp[amount], dp[n][m]). Sometimes the best over all cells.
Space saving: if a row only reads the previous row, keep two rows (or one), turning O(n·m) memory into O(m).
Top-down: easier to write, computes only reachable states, but limited by recursion depth. Bottom-up: no recursion limit, usually faster, easy to optimise memory, but you must get the order right and it computes every state.

See it move

Filling a knapsack table

Items have a weight w and a value v. Cell (i, c) holds the best value using the first i items with capacity c. Each cell either skips item i (copy the cell above) or takes it (its value plus the cell above-and-left by the item's weight). Yellow cells are the two it reads. Rows are filled top to bottom, so everything a cell needs already exists.

Worked by hand

Coin change as a table

Fewest coins to make 10 from coins 1, 5 and 6. Greedy (take the biggest first) gives 6 + 1 + 1 + 1 + 1 = 5 coins. The table finds better.

amount	0	1	2	3	4	5	6	7	8	9	10
fewest coins	0	1	2	3	4	1	1	2	3	4	2

1
How the last cell is computed
dp[10] tries each coin: coin 1 gives dp[9] + 1 = 5; coin 5 gives dp[5] + 1 = 2; coin 6 gives dp[4] + 1 = 5. The minimum is 2: five plus five.
2
How an earlier cell is computed

Implementation

1D tabulation: minimum coins

The table has one cell per amount. Impossible amounts stay at infinity.

Plan in plain steps

pseudocode

dp[0] = 0; every other amount starts at infinity
for amount a from 1 to target:
    for each coin c <= a:
        dp[a] = min(dp[a], dp[a - c] + 1)
answer: dp[target], or -1 if still infinity

python

def min_coins(coins, amount):
    INF = float("inf")
    dp = [0] + [INF] * amount
    for a in range(1, amount + 1):
        for c in coins:
            if c <= a  dp[a - c] +  < dp[a]:
                dp[a] = dp[a - c] + 
     -  dp[amount] == INF  dp[amount]

(([, , ], ))   
(([, , ], ))   
(([], ))   
(([], ))   
(([, , ], **))

Implementation

0/1 knapsack, one row, and the direction of the loop

Choose items, each at most once, to maximise value without exceeding capacity. The 2D table in the animation needs a row per item, but each row only reads the row above, so one array is enough, if the capacity loop runs downwards.

python

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

def unbounded(weights, values, cap):
    dp = [0] * (cap + 1)
    for wt, val in zip(weights, values):
        for c in range(wt, cap + ):             
            dp[c] = (dp[c], dp[c - wt] + val)
     dp[cap]

(([, , , ], [, , , ], ))   
(([], [], ))   
(([, ], [, ], ))   
(([, ], [, ], ))

Implementation

2D tables: LCS, edit distance, and an LIS shortcut

Two sequences give a natural 2D state: dp[i][j] for the first i characters of one and the first j of the other. The recurrence looks at the three neighbours up, left and diagonal, all of which are filled earlier in row-by-row order.

python

from bisect import bisect_left

def lcs(s, t):
    n, m = len(s), len(t)
    dp = [[0] * (m + 1) for _ in range(n + 1)]
    for i in range(1, n + 1):
        for j  (, m + ):
             s[i - ] == t[j - ]:
                dp[i][j] = dp[i - ][j - ] + 
            :
                dp[i][j] = (dp[i - ][j], dp[i][j - ])
     dp[n][m]

 (a, b):
    n, m = (a), (b)
    dp = [[] * (m + )  _  (n + )]
     i  (n + ):
        dp[i][] = i
     j  (m + ):
        dp[][j] = j
     i  (, n + ):
         j  (, m + ):
             a[i - ] == b[j - ]:
                dp[i][j] = dp[i - ][j - ]
            :
                dp[i][j] =  + (dp[i - ][j], dp[i][j - ], dp[i - ][j - ])
     dp[n][m]

 (a):
    tails = []
     x  a:
        i = (tails, x)
         i == (tails):
            tails.(x)
        :
            tails[i] = x
     (tails)

((, ))   
((, ))   
((, ))   
(([, , , , , , , ]))   
(([, , , , ]))

Implementation

Saving memory by keeping only what you read

If a cell depends only on the previous one or two cells, you do not need the whole table. Keep a couple of variables, or one row of a 2D table.

python

def house_robber(a):
    prev, cur = 0, 0
    for x in a:
        prev, cur = cur, max(cur, prev + x)
    return cur

def paths_in_grid(grid):
    R, C = len(grid), len(grid[0])
    row = [0] * C
    row[0] = 1 if grid[0][0] == "." else 0
    for r in range(R):
        for c in range(C):
            if grid[r][c] == "#":
                row[c] = 0
            elif c > :
                row[c] += row[c - ]
     row[-]

(([, , , , ]))   
(([]))   
(([, , ]))   
(([, , ]))

Complexity

Time and space of a table

As always, time = (number of states) × (work per state). Space = number of cells kept.

Knapsack-style time is pseudo-polynomial: it depends on the *value* of the capacity. That is fine for 10⁴ and impossible for 10⁹; then you need a different idea (for example, DP over value instead of weight, or meet-in-the-middle).

Coin change, minimum coins

time O(amount × coins)space O(amount)

One cell per amount; each tries every coin.

0/1 knapsack

time O(n × capacity)space O(capacity) with one row

n items, each updating every capacity once.

LCS / edit distance

time O(n × m)space O(n × m), or O(m) with two rows

One cell per pair of prefixes, O(1) work each.

LIS

time O(n²) simple, O(n log n) with tailsspace O(n)

n states each scanning earlier ones, or n binary searches.

Counting coin combinations

time O(amount × coins)space O(amount)

Same shape as minimum coins, but summing instead of minimising.

Knapsack when capacity is 10⁹

time infeasible as writtenspace -

The table size depends on the numeric value of capacity, not on n: pseudo-polynomial.

Edge cases

Amount or capacity 0Base case: 0 coins, value 0, one way (the empty selection). Make sure the loops handle it.
Unreachable statesUse infinity (minimise) or 0 ways (count) and convert at the end, e.g. -1.
Items heavier than the capacityThe loop range(cap, wt - 1, -1) is empty, so such items are skipped safely.
Empty inputA table with one base cell: handle it explicitly (house robber on an empty list is 0).
Off-by-one in 1-indexed tablesIn dp[i][j] the characters are s[i - 1] and t[j - 1]. Mixing the two conventions is the most common 2D DP bug.
Very large tablesA 10⁴ × 10⁴ table has 10⁸ cells, too much memory in Python. Use rolling rows, or rethink the state.
Order of the two loops in counting problemsCoins outside counts combinations; amounts outside counts orderings (see the worked problem).

Common mistakes

Mistakes to avoid

Looping capacity upwards in 0/1 knapsack with one row.
Go downwards so each item is used once; upwards turns it into unbounded knapsack.
Filling cells in an order where a dependency is not ready.
Write down which cells each cell reads, then choose loops so they come earlier.
Initialising every cell to 0 for a minimisation problem.
Unreachable states need infinity; 0 would claim they cost nothing.
Mixing up combinations and permutations when counting.
Coins in the outer loop for combinations, amounts in the outer loop for ordered sequences.
Reusing a rolling row after it was overwritten.
Only roll when the recurrence reads just the previous row (or two).
Forgetting the base row and column in 2D tables.

Recognize it in a contest

How to spot bottom-up DP problems

Reach for it when the problem says or implies

Knapsack shape: choose items with a size and a benefit under a capacity, or reach an exact sum (subset sum, partition, coin problems).
Two sequences compared prefix by prefix: longest common subsequence, edit distance, interleaving.
One sequence, best structure inside it: longest increasing subsequence, maximum subarray, house-robber (“no two adjacent”).
Grid paths: count or minimise paths moving only right and down, with obstacles or cell costs.
The state is small and numeric (amount up to 10⁴, lengths up to 2,000), and each state depends on smaller ones.
A recursive solution exists but depth would exceed 1,000, or you want to cut memory.

Look elsewhere when

Worked problem

Can the numbers be split into two equal halves?

The problem

Given a list of positive integers, decide whether it can be split into two groups with equal sums.

If the total is odd, the answer is No. Otherwise we need a subset whose sum is exactly total / 2.
That is subset sum, a knapsack with weight = value and exact-fit instead of maximise.
Let dp[s] mean “some subset adds to exactly s”. For each number, update from high sums to low so each number is used once.

python

def can_partition(nums):
    total = sum(nums)
    if total % 2:
        return False
    target = total // 2
    dp = [True] + [False] * target
    for x in nums:
        for s in range(target, x - 1, -1):
            dp[s] = dp[s] or dp[s - x]
    return dp[target]

print(can_partition([1, 5, 11, 5]))   
(([, , , ]))   
(([]))

Worked problem

Count the ways to make an amount

The problem

Given coin values (each usable any number of times) and a target, count the combinations of coins that sum to the target. Order does not matter: 1 + 2 and 2 + 1 are the same combination.

Let dp[a] be the number of ways to make a. dp[0] = 1 (the empty combination).
Process one coin at a time in the outer loop, and for each coin let dp[a] also include the ways that end by using that coin: dp[a] += dp[a - c].
Because coins are handled in a fixed order, each combination is built in only one order and is counted once. Swapping the loops (amounts outside) would count each order separately.

python

def coin_ways(coins, amount):
    dp = [1] + [0] * amount
    for c in coins:                          # coins outside: each combination counted once
        for a in range(c, amount + 1):
            dp[a] += dp[a - c]
    return dp[amount]

 (coins, amount):
    dp = [] + [] * amount
     a  (, amount + ):           
         c  coins:
             c <= a:
                dp[a] += dp[a - c]
     dp[amount]

(([, , ], ))   
(([], ))   
(([], ))   
(([, ], ))

Wrap-up

Remember this

Bottom-up DP computes the same states as memoization, but with loops in a chosen order and a table instead of recursion.
Write the same state, base case and transition, then choose a fill order so every dependency is ready.
In 0/1 knapsack the capacity loop runs downwards so each item is used once; upwards allows reuse.
2D tables handle two sequences (LCS, edit distance) and grids; rolling rows cut memory when only the previous row is read.
Time is states × work per state; knapsack-style tables are pseudo-polynomial in the capacity.

Cheat sheet

Tabulation: table of states · base cells · loops in dependency order · answer cell
Min coins: dp[a] = min(dp[a − c] + 1); unreachable = ∞
0/1 knapsack: for each item: for c from cap down to wt: dp[c] = max(dp[c], dp[c − wt] + val)
Unbounded: same, but c runs upward
Count combinations: coins outside, amounts inside; dp[0] = 1
Rolling space: keep only the rows the recurrence reads

Top traps to avoid

Looping capacity upwards in 0/1 knapsack with one row.
Filling cells in an order where a dependency is not ready.
Initialising every cell to 0 for a minimisation problem.

Mastery check

0 of 15 answered

Answer from understanding, not memory of the page. You need 12 of 15. Each answer is explained, and you can retry as often as you like.

1.What is the main practical advantage of bottom-up DP over memoized recursion in Python?
2.For coins [1, 5, 6], what is dp[7] (fewest coins for 7)?
3.In 0/1 knapsack with a single 1D array, why must the capacity loop run from high to low?
4.What is the time complexity of 0/1 knapsack with n items and capacity W?
5.“Find the length of the longest common subsequence of two strings” is best solved with:
6.coin_ways([1, 2], 3) counts combinations (order ignored). What does it return?
7.0/1 knapsack: weights [1, 3, 4], values [15, 20, 30], capacity 4. What is the best value?
8.Length of the longest increasing subsequence of [10, 9, 2, 5, 3, 7, 101, 18]?
9.Edit distance between 'kitten' and 'sitting' (insert, delete, replace each cost 1). What is printed?
10.Why does a bottom-up table avoid recursion overhead?
11.0/1 knapsack with n items and capacity W, bottom-up: what is the time?
12.Subset sum: can [1, 5, 11, 5] be split into parts with sum 11 (a subset summing to 11 exists)?
13.Longest common subsequence of 'abcde' and 'ace'. What is printed?
14.Paths from the top-left to the bottom-right of a 3x3 grid moving only right or down. How many are there?
15.When filling a bottom-up table, what order must you follow?

dp[7]: coin 1 gives dp[6] + 1 = 2; coin 5 gives dp[2] + 1 = 3; coin 6 gives dp[1] + 1 = 2. Minimum 2: six plus one.

Dynamic Programming: Bottom-Up (Tabulation, Knapsack)

After this lesson you will be able to

Builds on

Unlocks

Climbing the stairs from the bottom

Recursion that memoizes, but still recurses

If you know the order, you do not need the recursion

The tabulation recipe, and top-down versus bottom-up

Filling a knapsack table

Coin change as a table

1D tabulation: minimum coins

0/1 knapsack, one row, and the direction of the loop

2D tables: LCS, edit distance, and an LIS shortcut

Saving memory by keeping only what you read

Time and space of a table

Edge cases

Mistakes to avoid

How to spot bottom-up DP problems

Can the numbers be split into two equal halves?

Count the ways to make an amount

Wrap-up

Remember this

Cheat sheet

Top traps to avoid

Mastery check

Practice this topic

Core1 problem

Application2 problems

Reading the code

Reading the code

Reading the code

Reading the code