Dynamic Programming 1D 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 problem of the module. Decide the state and the transition first, then write the table.
Choose the state and the transition first
Before any code, write one sentence: dp[i] is the best, fewest or number of something for the first i items, or for amount i. Then write how the last choice leads back to a smaller cell.
# stairs: dp[i] = ways to reach step i# robber: dp[i] = best total for the first i houses# coins: dp[a] = fewest coins for amount a# LIS: dp[i] = longest run ending at item iprint("state first")Example 1 · Which problem is it
# a bank allows steps of 1 or 2 days between payments; count the ways to cover 5 daysdp = [1, 1]for i in range(2, 6): dp.append(dp[-1] + dp[-2])print(dp[5])
# the fewest payments from 2, 5 and 6 to make 10INF = float("inf")best = [0] + [INF] * 10for a in range(1, 11): for c in (2, 5, 6): if c <= a: best[a] = min(best[a], best[a - c] + 1)print(best[10])8 2
What this code does
- The first is a counting table with two earlier cells. The second is a minimum over coins.
- Reading the clue (ways, or fewest with unlimited items) picks the shape.
These four sentences are the whole design. If you cannot say the state in one sentence, the table will not work.
Match the clue to the problem
Count the ways or best total with a few earlier cells: stairs and robber. An amount and unlimited items: coin change. Rising order with skips: longest increasing subsequence. A string cut into pieces: prefix tables.
from bisect import bisect_left
tails = []for x in [3, 1, 2, 5, 4]: k = bisect_left(tails, x) tails[k:k + 1] = [x]print(len(tails))Example 2 · Check fast against slow
from bisect import bisect_leftimport random
def rob(m): prev, best = 0, 0 for x in m: prev, best = best, max(best, prev + x) return best
def rob_slow(m, i=0): if i >= len(m): return 0 return max(rob_slow(m, i + 1), m[i] + rob_slow(m, i + 2))
random.seed(3)ok = all(rob(m) == rob_slow(m) for m in ([random.randint(0, 9) for _ in range(random.randint(0, 10))] for _ in range(100)))print(ok)True
What this code does
- A slow recursion on small lists is the easiest test for a fast table.
- Both give the same answer on 100 random lists.
Example 3 · A mixed problem
from bisect import bisect_left
prices = [7, 3, 5, 2, 8, 6, 9]tails = []for x in prices: k = bisect_left(tails, x) if k == len(tails): tails.append(x) else: tails[k] = xprint(len(tails), len(prices) - len(tails))4 3
What this code does
- The longest rising run is 4, for example 3, 5, 8, 9, and 3 items must be removed to leave a rising list.
- Both answers come from one pass, so time is O(n log n).
tails[k:k + 1] = [x] replaces slot k, or appends when k equals the length, so one line covers both cases. Check this with a short list before using it.
State the cost
Say time and space in plain words: a table of n cells filled with constant work is O(n) time and space; coin change is O(amount x coins); the tails method is O(n log n). Then say whether two variables are enough.
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
Print the number of ways to climb 8 steps with moves of 1 or 2.
34
Exercise 2· Easy
Print the best total for the houses [1, 2, 3, 1] with no two neighbours taken.
4
Exercise 3· Medium
Print the fewest coins that pay 9 with coins 2, 3 and 7.
2
Exercise 4· Medium
Print the number of sets of coins 2, 3 and 5 that pay 10.
4
Exercise 5· Medium
Print the longest strictly increasing subsequence length of [0, 8, 4, 12, 2, 10, 6, 14, 1, 9].
4
Exercise 6· Hard
Print whether "applepenapple" can be cut into the words apple and pen, then the number of ways to decode "1212".
True 5
Exercise 7· Hard
Houses in a circle hold [9, 3, 1, 9, 4]. Print the best total.
18
Exercise 8· Hard
Print the fewest coins for 11 with coins 1, 5 and 6, then the coin list used, sorted.
2 [5, 6]
Interview questions
Questions interviewers ask on this topic.
Finish up
Mark complete & continue
Next: Must-do problems: Dynamic Programming (1D)