2D Dynamic Programming Checkpoint
A review of this module. Skip it if you feel confident; the next module does not need it.
Fix the mistakes
The slips that cost marks in this module. Spot each one, then check the fix.
This checkpoint mixes every table in the module. Decide first what the state means, then the fill order and the answer cell, then write the code.
Name the state first
Before any code, say in one sentence what dp[i][j] means. For a grid it is a cell, for knapsack it is items and capacity, for two strings it is two prefix lengths, and for a range problem it is the range i to j. Here size[r][c] is the side of the largest square of 1s ending at that cell.
def largest_square(grid): best = 0 size = [[0] * len(grid[0]) for _ in grid] for r, row in enumerate(grid): for c, cell in enumerate(row): if cell == 1: if r and c: size[r][c] = 1 + min(size[r - 1][c], size[r][c - 1], size[r - 1][c - 1]) else: size[r][c] = 1 best = max(best, size[r][c]) return bestExample 1 · Largest square of ones
def largest_square(grid): best = 0 size = [[0] * len(grid[0]) for _ in grid] for r, row in enumerate(grid): for c, cell in enumerate(row): if cell == 1: if r and c: size[r][c] = 1 + min(size[r - 1][c], size[r][c - 1], size[r - 1][c - 1]) else: size[r][c] = 1 best = max(best, size[r][c]) return best
grid = [ [1, 0, 1, 1], [1, 1, 1, 1], [0, 1, 1, 1],]print(largest_square(grid))2
What this code does
- A 2 by 2 block of ones sits at the bottom right. A 3 by 3 square would need a 1 in the bottom-left cell and in the top row, but those cells are 0.
- Each cell looks at three neighbours, so the cost is O(rows x cols).
A cell is the corner of a square only if the three neighbours above, left and diagonal are all corners of squares. The smallest of them limits the size.
Fill order and space
Prefix tables fill row by row. Range tables fill by length, or by i from the end. Mask tables fill by increasing mask. When a row reads only the row before it, keep one or two rows. Keep the full table if you must rebuild the answer.
Example 2 · Count subsets with one row
nums = [1, 2, 3, 3, 4]target = 6ways = [0] * (target + 1)ways[0] = 1for x in nums: for s in range(target, x - 1, -1): ways[s] += ways[s - x]print(ways[target])4
What this code does
- ways[s] counts the subsets that add up to s. Looping downwards uses every number once.
- Four subsets reach 6: 1+2+3 (twice, once per 3), 2+4 and 3+3.
Check the base case and the answer cell
Most wrong answers come from the edges: the empty prefix, the first row, a range of length one, or the mask 0. Decide what the answer cell is: the bottom-right corner, the last row and full capacity, or the full mask. Then test on the smallest possible input.
Example 3 · Shortest string with both as subsequences
def lcs(a, b): prev = [0] * (len(b) + 1) for x in a: cur = [0] for j, y in enumerate(b, 1): cur.append(prev[j - 1] + 1 if x == y else max(prev[j], cur[j - 1])) prev = cur return prev[-1]
a, b = "geek", "eke"print(len(a) + len(b) - lcs(a, b))5
What this code does
- Letters in the common subsequence are written once, so the length is len(a) + len(b) - LCS.
- Here LCS is 2, so the shortest string has 4 + 3 - 2 = 5 letters.
Module quiz
Questions from the whole module. Your first answer is your score.
Problems
Graded easy to hard, using everything from this module.
Try each one yourself first. Use the hint if you get stuck. Mark it as done when it works.
Exercise 1· Easy
Build a grid with 2 rows and 3 columns of zeros, set the first cell to 1, and print the grid. Rows must be independent.
[[1, 0, 0], [0, 0, 0]]
Exercise 2· Easy
Print the longest common subsequence length of "ABCDE" and "ACE".
3
Exercise 3· Easy
Print True or False: can some of [8, 6, 7, 5, 3, 10, 9] add up to 15?
True
Exercise 4· Medium
Print the side of the largest square of 1s in [[1, 0, 1, 0, 0], [1, 0, 1, 1, 1], [1, 1, 1, 1, 1], [1, 0, 0, 1, 0]].
2
Exercise 5· Medium
Print the edit distance between "horse" and "ros".
3
Exercise 6· Medium
Print the best value for weights [5, 4, 6, 3], values [10, 40, 30, 50] and capacity 10, using one list.
90
Exercise 7· Hard
Print the cheapest number of multiplications for matrices described by the sizes [30, 35, 15, 5, 10, 20, 25].
15125
Exercise 8· Hard
Print the cheapest total for giving 4 workers 4 different jobs with [[14, 5, 8, 7], [2, 12, 6, 5], [7, 8, 3, 9], [2, 4, 6, 10]], using a mask over the jobs.
15
Interview questions
Questions interviewers ask on this topic.
Finish up
Mark complete & continue
Next: Must-do problems: 2D Dynamic Programming