Knapsack and grid paths in Python

Why it matters

Some problems need two numbers to describe one subproblem. A robot standing at row 2, column 4 of a grid is one example: the two numbers are its position. A thief who has looked at the first 3 items and has 10 kilograms of space left is another: the two numbers are "how many items have been considered" and "how much room is left". When the state has two numbers, the table becomes two-dimensional. The recipe from the first lesson still applies, but you write the state with two indexes and fill the table in a careful order.

This lesson covers two standard problems. Grid paths is the friendliest entry point, because the state is a position you can picture. The 0/1 knapsack is one of the most important problems in the whole subject. Greedy methods fail on it, many interview questions are variations of it, and it shows the single most important loop detail in DP: the direction of a loop decides whether an item can be used once or many times.

You should have finished the first two lessons. You should be able to fill a one-dimensional table and read the result. Every program in this lesson is a plain Python file. The programs marked python run print their output without reading input. Where a program reads input, the lesson says what to type when it asks.

Grid paths: the robot picture

Imagine a robot in the top-left corner of a warehouse floor. The floor is a grid with m rows and n columns. The robot can move only one way: right, or down. It cannot move left or up. The robot must reach the bottom-right corner. How many different routes can it take?

Start with a small grid, 2 rows and 2 columns. The robot needs exactly one right move and one down move. It can do them in two orders: right then down, or down then right. So there are 2 routes. Now try 3 rows and 3 columns. The robot needs 2 right moves and 2 down moves in some order. There are 4 moves, and we must choose which 2 of the 4 are the down moves. That is 6 routes. The counting gets harder as the grid grows, and a loop that tries every route is too slow. DP gives a faster answer.

The state and the recurrence

State: dp[r][c] is the number of routes from the top-left corner to the cell in row r, column c. Both r and c are needed, because the position is two numbers. In Python, dp[r][c] means the item at position c inside the list at position r. A list of lists like this is the usual way to make a two-dimensional table.

Recurrence: a route that reaches cell (r, c) must have arrived from the cell above it, (r - 1, c), or from the cell to its left, (r, c - 1). No other cell can move into (r, c), because the robot only moves right or down. So the number of routes into (r, c) is the sum of the routes into those two cells:

dp[r][c] = dp[r - 1][c] + dp[r][c - 1]

Base cases: the first row and the first column each have exactly one route. In the first row, the robot has only moved right, so there is one route to each cell. In the first column, the robot has only moved down, which is also one route. These cells have no cell above or no cell to the left, so the recurrence cannot be used for them.

Order: fill the table row by row from top to bottom, and inside each row from left to right. Every cell reads the cell above it, which is in the previous row, and the cell to its left, which is earlier in the same row. Both are filled before the current cell.

The table for a 3 by 3 grid

Here is the completed table. Each cell shows the number of routes to that cell.

Check one cell by hand. The cell at row 1, column 1 is dp[0][1] + dp[1][0] = 1 + 1 = 2. The cell at row 2, column 2 is dp[1][2] + dp[2][1] = 3 + 3 = 6, which matches the count you found by thinking about the 4 moves. The bottom-right corner is the answer.

Saving memory: one row at a time

Each row of the table needs only the row above it. So you can keep a single list of length n and update it in place. The first row is all 1s. For each later row, the cell at column c becomes the old value at column c (the cell above, which is still there) plus the new value at column c - 1 (the cell to its left, already updated in this row). In code, dp[c] += dp[c - 1]. This is one of the most common space savings in DP, and it is worth recognising at a glance.

The code for unique paths

The next program reads the number of rows and columns from the input. It uses the one-row version, so the memory is O(n) instead of O(m * n). Type this when it asks for input:

3 7

def unique_paths(m, n):
    dp = [1] * n
    for r in range(1, m):
        for c in range(1, n):
            dp[c] += dp[c - 1]
    return dp[n - 1]
 
 
m, n = map(int, input().split())
print("paths:", unique_paths(m, n))

The output is:

paths: 28

The first number is the rows and the second is the columns, so 3 7 is a grid with 3 rows and 7 columns. The reversed order gives the same answer here, because the count is symmetric, but in harder problems the order matters, so always read the statement. The function map(int, input().split()) turns the two pieces of text into two whole numbers, and the line m, n = ... puts them into two names at once.

Look at the loops. [1] * n sets the first row to all 1s. The outer loop starts at row 1 because row 0 is already done. The inner loop starts at column 1 because column 0 is always 1, and it is never changed. Inside the loop, dp[c] already holds the value from the row above, and dp[c - 1] already holds the new value in this row. The sum gives the new dp[c].

The next program builds the full two-dimensional table, so you can see every cell for a 3 by 3 grid. It does not read input.

The output is:

[[1, 1, 1], [1, 2, 3], [1, 3, 6]]
6

The second line uses comb from the math module, which gives the number of ways to choose items from a set. It is explained in the interview section.

Minimum path sum: when each cell has a cost

A common variation puts a cost on every cell. The robot must pay the cost of each cell it enters, and it wants the cheapest route. The state is the same, but the recurrence changes. Instead of counting routes, we keep the smallest total cost to reach each cell.

State: dp[r][c] is the smallest total cost of a route from the top-left corner to cell (r, c), including the cost of that cell. Recurrence: the robot arrived from above or from the left, so dp[r][c] = cost[r][c] + min(dp[r - 1][c], dp[r][c - 1]). Base cases: the top-left cell has dp = cost, and each cell in the first row or first column has only one way in, so its value is the sum of costs so far. Order: the same as before, row by row.

Here is a small cost grid:

1 3 1
1 5 1
4 2 1

Fill the table. The first row is 1, 4, 5, because each cell adds its cost to the one before. The first column is 1, 2, 6. Now the middle row. Cell (1, 1) costs 5, and it can be reached from above (4) or from the left (2). It takes the smaller, 2, and adds 5, giving 7. Cell (1, 2) costs 1 and can be reached from above (5) or from the left (7). It takes 5 and adds 1, giving 6. The last row gives 6, 8, 7. So the completed table is:

1 4 5
2 7 6
6 8 7

The bottom-right value is 7. The cheapest route is right, right, down, down: the costs 1, 3, 1, 1, 1 add to 7. The program below computes the same table and prints it, so you can compare each cell with the hand trace.

The output is:

[[1, 4, 5], [2, 7, 6], [6, 8, 7]]
cheapest: 7
[[2, 3], [3, 12], [4, 5]]

The printed table matches the hand trace exactly. Python prints a list of lists with nested brackets, which is how you should look at any two-dimensional table while you debug.

Notice that the first row and first column are filled before the nested loops. Those cells have only one way in, so they need their own formulas. Look at the line dp = [[0] * n for _ in range(m)]. It builds a separate row for each _. Writing [[0] * n] * m would not work, because every row would be the same list object, and a change to one cell would show up in every row. The common mistakes section shows this.

0/1 knapsack: the packing problem

Now the knapsack problem. Imagine a hiker with a backpack that can carry at most a certain weight. There are several items in a shop. Each item has a weight and a value to the hiker. The hiker can take each item whole, or leave it. The hiker cannot take half of an item, and cannot take the same item twice. The goal is to pack the bag so the total value is as large as possible without going over the weight limit.

This is called the 0/1 knapsack. The name means each item is either 0 (left out) or 1 (taken whole). The bag is the knapsack. The weight limit is the capacity.

Why greedy fails

A tempting idea is to sort the items by value per kilogram, then take the best ones first until the bag is full. This is greedy. It works if you may take parts of items, because you can always fill the last bit of space. It fails for whole items. Here is a counterexample with three items and a capacity of 50.

Greedy takes A, which uses 10 of the 50 units, then B, which uses 20 more, for a total of 30 and a value of 160. Item C no longer fits, because 30 more would make 60. But the best choice is B and C together. They weigh exactly 50 and are worth 220. Greedy is 60 short. The cause is that A's good ratio used up space that a better pair needed. Only a method that checks combinations, as DP does, finds 220.

The state and the recurrence

To solve this with DP, we need a state that captures the decision. The useful state is: "using only the first i items, with a capacity of w, what is the best value?" That has two numbers: how many items have been considered, and how much room there is.

State: dp[i][w] is the best total value that can be packed from the first i items into a bag with capacity w.

Recurrence: consider item i (the one at position i in the list, counting from 1). It has weight wt and value val. There are two options.

• Skip it. The value is the best we could do without this item: dp[i - 1][w].
• Take it. This needs wt <= w. We get val for the item, plus the best from the first i - 1 items with the remaining space w - wt: dp[i - 1][w - wt] + val.

We take the larger of the two: dp[i][w] = max(dp[i - 1][w], dp[i - 1][w - wt] + val). If wt is bigger than w, the item cannot fit, so only the skip option exists.

Base cases: with zero items, the value is 0 for every capacity, so dp[0][w] = 0. With zero capacity, the value is 0 for every number of items, so dp[i][0] = 0.

Order: row by row, from i = 1 up to the number of items, and within each row any order of w works, because each cell reads only the row above.

A trace on a small example

Use four items with weights and values (1, 1), (3, 4), (4, 5) and (5, 7), and a capacity of 7. The best answer is 9, from the items with weights 3 and 4. Here is the start of the full table, for capacities 0 to 7, showing the first three items. Read each row as "the best value for the first i items at each capacity".

Check the last column by hand. At capacity 7 with items 1 to 3, the best is 9. How? Item 3 has weight 4 and value 5. Taking it leaves capacity 3 for items 1 and 2, and the best at capacity 3 is 4 (item 2 alone). So 5 + 4 = 9. Skipping item 3 would give 5 (items 1 and 2 at capacity 7), so 9 is larger. The formula chose the larger option at each cell.

Notice the value 6 at capacity 5 and again at capacity 6. The 6 comes from items 1 and 3 together (weights 1 and 4, total 5, value 1 + 5 = 6). The extra unit of room at capacity 6 cannot add anything, so the cell keeps the same 6.

The 1D version, and why the loop goes downward

The 2D table has a row for each item. Like the grid, each row reads only the row above it, so we can keep a single list dp[w]. Start with all zeros. For each item, update the list so that dp[w] becomes max(dp[w], dp[w - wt] + val). The question is the order in which w is visited, and this is where most bugs in knapsack code live.

The value dp[w - wt] must still hold the value from before this item was processed. That is what the formula needs: the best of the earlier items. If w runs downward, from the largest capacity to wt, then when we reach w, the cell w - wt is smaller than w, so it has not been updated yet for this item. It still holds the old value. Each item is used at most once.

If w ran upward, the cell w - wt would already include this item, because it was updated earlier in the same loop. The formula would then add the item again. The item would be used many times. That turns the 0/1 knapsack into a different problem, the unbounded knapsack, where each item can repeat. Both problems are real, and the difference is one loop direction.

The code for knapsack

The next program reads the number of items and the capacity on the first line, then one line per item with its weight and value. It uses the 1D version with the downward loop. Type these lines when it asks for input:

4 7
1 1
3 4
4 5
5 7

def knapsack(wt, val, capacity):
    dp = [0] * (capacity + 1)
    for i in range(len(wt)):
        for w in range(capacity, wt[i] - 1, -1):
            dp[w] = max(dp[w], dp[w - wt[i]] + val[i])
    return dp[capacity]
 
 
n, capacity = map(int, input().split())
wt = []
val = []
for _ in range(n):
    w, v = map(int, input().split())
    wt.append(w)
    val.append(v)
print("best value:", knapsack(wt, val, capacity))

The output is:

best value: 9

The first line says there are 4 items and the capacity is 7. Each following line is a weight and then a value. The loop for _ in range(n) reads one line per item. Notice the range in the inner loop: range(capacity, wt[i] - 1, -1) counts down from the capacity to wt[i], and it stops before wt[i] - 1. So it never reads dp[w - wt[i]] with a negative index. That stopping point is what makes the loop safe.

The list has capacity + 1 cells, so capacity 7 needs index 7 to exist. That is why the list size adds 1, the same rule you saw for stairs in the first lesson.

Recovering which items were taken

Interviewers often ask for the list of items, not only the total. To recover them, you need the whole 2D table, because the 1D list has already lost the history. Walk backward from the bottom-right cell. For item i at the current capacity w, if dp[i][w] differs from dp[i - 1][w], then item i must have been taken, because only taking it changed the value. Then move to row i - 1 with capacity w - wt. If the two values are the same, the item was skipped, so stay at capacity w and move up one row.

The program below does this for the example. It prints the best value and the chosen items. It also uses the 2D table on purpose, because the walk back needs it. It does not read input.

The output is:

best value: 9
take item 3 (weight 4, value 5)
take item 2 (weight 3, value 4)

The walk back starts at item 4 with capacity 7. The table says dp[4][7] = 9 and dp[3][7] = 9, so item 4 was skipped. Item 3 gives dp[3][7] = 9 and dp[2][7] = 5, so item 3 was taken, and the capacity drops to 3. At item 2 with capacity 3, dp[2][3] = 4 and dp[1][3] = 1, so item 2 was taken, and the capacity drops to 0. Item 1 is never taken because the capacity is 0.

The items appear in the output from last to first, because the walk back goes that way. If you need them in order, store them in a list and call reverse() on it. This is a common follow-up question, and it shows that you understand the table, not only the number.

The unbounded knapsack contrast

Here is a program that shows the loop-direction bug on purpose. It runs the same item twice, once with the correct downward loop and once with an upward loop, for one item of weight 1 and value 10 with capacity 3. The correct answer is 10, because the bag can hold only one of the item. The wrong loop gives 30, because it places the same item three times.

The output is:

0/1 loop (downward): 10
upward loop:         30

Trace the upward version. dp[1] = 10. Then dp[2] = dp[1] + 10 = 20, because dp[1] already contains the item. Then dp[3] = dp[2] + 10 = 30. The item is counted three times. A bag of capacity 3 can hold three of the item in this wrong model, which is not the problem we were given.

The downward version gives dp[3] = 10, which is correct. The lesson is simple to remember: for 0/1 knapsack, the capacity loop goes from high to low. For unlimited copies of an item, it goes from low to high. Interviewers test this distinction directly.

Two-dimensional state: when to use it

You can recognise a two-parameter DP from the words in the problem. If the statement mentions a position in a grid, two strings, a range of indexes, or an item together with a limit, the state probably has two numbers. Write the state in words with both numbers. For example: "dp[i][w] is the best value using the first i items with capacity w."

A table with two indexes costs more memory than one with one index. For a grid of size m by n, the full table has m * n cells. Shrinking to one row, as in unique paths, cuts that to n, and it works only when each row reads only the row above. Knapsack shrinks the same way. Check the dependency before you shrink, because a cell that reads the cell to its right would need a different order.

Why the knapsack is pseudo-polynomial

The running time O(n * capacity) looks like a clear bound, but it hides a trap. The time depends on the value of the capacity, not only on how many items there are. Interviewers like to ask about this, so here is a concrete picture.

Suppose there are 20 items and the capacity is 100. The table has 20 times 101 cells, about 2,000 steps, which is instant. Now suppose the capacity is 1,000,000,000 (a billion). The table would need 20 billion cells, which is far too much memory and far too slow. The number of items is still 20, but the work has grown with the size of the capacity number.

Compare this with a true polynomial algorithm. Its time depends on the size of the input, measured in the number of characters needed to write it. A capacity of a billion needs only 10 characters to write, but the table needs a billion cells. That mismatch is why the algorithm is called pseudo-polynomial. It is fast when the capacity is small, which is the common case in practice, and slow when the numbers in the input are huge.

The honest answer in an interview has three parts. State the time as O(n * capacity). Say that the algorithm is pseudo-polynomial, and explain that the time depends on the value of the capacity. Offer the usual fix when the capacity is huge: scale the weights down if the problem allows it, or use a different method. You do not need a full solution for the large case, but you should show that you know the limit exists.

Common mistakes

Mistake 1: looping the knapsack capacity upward. This gives the unbounded answer, as the contrast program shows. The fix is to loop from the capacity down to the weight of the item.

Mistake 2: forgetting the first row and first column in grid DP. This mistake is quiet in Python. Python accepts a negative list index and counts from the end of the list, so dp[r - 1] with r equal to 0 reads the last row, not an error. The program below starts both loops at 0 and uses the same formula everywhere.

def min_path_table_bad(cost):
    m, n = len(cost), len(cost[0])
    dp = [[0] * n for _ in range(m)]
    for r in range(m):
        for c in range(n):
            dp[r][c] = cost[r][c] + min(dp[r - 1][c], dp[r][c - 1])
    return dp
 
 
print(min_path_table_bad([[1, 3, 1], [1, 5, 1], [4, 2, 1]]))

It prints [[1, 3, 1], [1, 6, 2], [4, 6, 3]] and raises no error. The bottom-right value is 3, but the correct answer is 7. The first cell already reads the wrong cells, and every later cell inherits the mistake. This is why printing the table and comparing it with a hand trace matters more in Python than an error message does. Fill the first row and column with their own formulas first, as the lesson shows.

Mistake 3: mixing up rows and columns. A grid with 3 rows and 7 columns has dp[r][c] with r up to 2 and c up to 6. If you swap the two numbers when you create the list, the table has the wrong shape. A quick check is to print len(dp) (the number of rows) and len(dp[0]) (the number of columns) before you fill it.

Mistake 4: a list of lists that shares its rows. The expression [[0] * n] * m looks right, but it makes m references to one row. Setting one cell changes every row. The next program shows it.

The output is [[5, 0, 0], [5, 0, 0]]. Write [[0] * n for _ in range(m)] instead, which creates a new row each time.

Mistake 5: trying greedy on whole items. The counterexample with items of value 60, 100 and 120 shows why. Whenever the items are whole, a greedy choice that looks best can block a better combination. If the problem says "you can take part of an item", greedy is correct. If it says "each item is taken whole", use DP.

Mistake 6: forgetting that the table must have capacity plus one cells. A list of size capacity cannot hold index capacity. The program below makes that mistake and prints the error.

capacity = 7
dp = [0] * capacity
dp[capacity] = 1

The error is IndexError: list assignment index out of range, and the fix is [0] * (capacity + 1).

Mistake 7: reading dp[w - wt] when wt is bigger than w. The range in the loop prevents this. If you rewrite the loop as for w in range(capacity, -1, -1): you must add an if check before reading dp[w - wt[i]]. Without the check, Python does not raise an error for a negative index. It reads a cell near the end of the list, and the answer comes out wrong. The next program shows the wrong answer.

The output is 26, but the answer for the same items is 9. The loop read dp[-1], dp[-2] and so on, which are cells from the end of the list. Add the check if wt[i] <= w: before the update to fix it.

Debugging a two-dimensional table

When a grid or knapsack answer is wrong, print the table, as the minimum path sum program does. Then compare each cell with the hand trace, in the same order you filled the table. The first wrong cell is the bug. For knapsack, check the first item row before anything else, because a mistake there spreads to every later row.

Another useful habit is to test a tiny input where the answer is obvious. For knapsack, use one item that fits and one that does not. For the grid, use a 1 by 1 grid, which has one path, and a 1 by 3 grid, which also has one path. These small tests catch base-case bugs, which are the most common errors in two-dimensional DP.

Edge cases you should test

• Grid: a 1 by 1 grid has 1 path and cost equal to its single cell. A 1 by n or m by 1 grid has exactly 1 path.
• Grid: a grid full of zero costs has total cost 0.
• Knapsack: capacity 0 gives value 0. An item heavier than the capacity is never taken.
• Knapsack: items that all fit give the sum of all values.
• Knapsack: equal ratios, such as two items with the same value per kilogram, are not a special case for DP. The table handles them without any extra code.

Write these tests before you write the code. Interviewers like candidates who name the base cases first.

Interview questions you should expect

"What is the time and space complexity of 0/1 knapsack?" Time is O(n * capacity), because each item visits each capacity once. Space is O(capacity) with the 1D version, or O(n * capacity) with the full table. Explain that this is pseudo-polynomial. The time depends on the value of the capacity, not only on the number of items. A capacity of a billion makes the table impossible, even with few items.

"How would you return the chosen items?" Keep the full 2D table, then walk back from the bottom-right corner as the recovery program does. If the table is too big, you can recompute rows as needed, but explain the trade-off.

"What changes for unlimited copies of each item?" Loop the capacity upward. The unbounded knapsack and the 0/1 knapsack differ in one line.

"Why does greedy fail for knapsack but work for fractional knapsack?" Fractional items can fill the last gap exactly, so the best ratio always wins. Whole items can leave gaps that a worse-ratio combination would fill. Give the counterexample with items 60, 100 and 120.

"How many paths in an m by n grid?" The answer is the binomial coefficient C(m + n - 2, m - 1), which counts the ways to choose which moves are downward. In Python this is math.comb(m + n - 2, m - 1). The DP table gives the same answer and is easier to explain when the grid has obstacles, where the formula no longer works.

Practice

Try these before reading the solutions. Work each one by hand first, then check with the programs.

Exercise 1 (easy). Fill the grid path table for a 2 by 2 grid. How many paths are there?

Show the answer

The table is 1 1 on the first row and 1 2 on the second. The bottom-right cell is 2, so there are 2 paths: right then down, and down then right.

Exercise 2 (easy). Knapsack with weights {2, 3}, values {3, 4}, and capacity 4. Which items can be taken, and what is the best value?

Show the answer

The two items weigh 5 together, which is more than 4, so they cannot both be taken. Taking only the item of weight 3 gives value 4. Taking only the item of weight 2 gives 3. The best value is 4.

Exercise 3 (easy). Write the base cases for the grid path table and say why the first row has no recurrence.

Show the answer

Every cell in row 0 and column 0 has exactly one route, so its value is 1. The first row has no recurrence, because a cell in row 0 has no cell above it. The recurrence needs both the cell above and the cell to the left. Cells in the first row have only the cell to the left, and the first column has only the cell above, so the formula cannot be applied as written.

Exercise 4 (medium). Compute the minimum path sum for the cost grid [[2, 1], [1, 9], [1, 1]]. Give the table and the answer.

Show the answer

Row 0: 2, then 2 + 1 = 3. Row 1: first cell 2 + 1 = 3; second cell 9 + min(3, 3) = 12. Row 2: first cell 3 + 1 = 4; second cell 1 + min(12, 4) = 5. The table is [[2, 3], [3, 12], [4, 5]], and the answer is 5. The cheapest route goes down the left column, then right. The program above prints the same table.

Exercise 5 (medium). Using the knapsack table from the lesson, what is the best value at capacity 6 using only the first two items?

Show the answer

Look at the row for items 1 to 2 at capacity 6. The value is 5. Items 1 and 2 weigh 4 together, so both fit, giving 1 + 4 = 5. The value 6 appears only once the third item is included.

Exercise 6 (medium). Explain in two sentences why the downward capacity loop prevents an item from being used twice.

Show the answer

When the loop reaches capacity w, the cell w - wt is smaller than w, so the loop has not yet visited it in this pass, and it still holds the value from before this item. The formula therefore adds the item to a state that never contained it.

Exercise 7 (medium). The greedy value-per-kilogram method picks A then B in the lesson's counterexample. Find a two-item combination that the greedy method misses, and state its value.

Show the answer

B and C together weigh 50 and are worth 220. Greedy never considers that pair, because after taking A it cannot fit C. So the pair of B and C, with value 220, is the combination greedy misses.

Exercise 8 (hard). A grid has obstacles that you cannot enter, marked as 1, and free cells marked as 0. Write the recurrence for the number of paths, and say what the value of an obstacle cell is.

Show the answer

An obstacle cell has 0 paths into it, so dp[r][c] = 0 when the cell is an obstacle. For a free cell, the recurrence stays dp[r][c] = dp[r - 1][c] + dp[r][c - 1], but any cell outside the grid counts as 0. The first row and column stop counting once an obstacle appears, because nothing can pass through it. Check the start cell too: if it is an obstacle, the answer is 0.

Exercise 9 (hard). Explain why the 2D knapsack table can be reduced to one row, but the 0/1 walk-back needs the full table. What would you have to store to recover the items from the 1D list alone?

Show the answer

The 1D list keeps only the latest row, so the earlier rows that the walk back needs are overwritten. Each row reads only the row before it, so the value at the end is correct, but the history is gone. To recover items from a 1D list you would store one decision bit per item and capacity, which costs the same n * capacity memory as the full table, or recompute the rows backward, which costs more time. That is why the walk back uses the full table in this lesson.

What you now know

• Two-parameter DP uses a table with two indexes, one for each number in the state.
• Grid paths add the cell above and the cell to the left. Minimum path sum adds the cell's cost to the smaller of those two.
• The 0/1 knapsack chooses between skipping an item and taking it, and greedy can fail because items are whole.
• The 1D knapsack loop goes downward, so each item is used at most once.
• To recover the chosen items, keep the full table and walk back from the bottom-right corner.
• Python does not stop on a negative index, so a wrong answer can come with no error. Print the table and check it cell by cell, starting from the first row.