The question this module answers: what if the recursion tree is huge, but the number of distinct subproblems is small? Lesson 8.1 showed naive Fibonacci recomputing the same calls exponentially often, and memoisation collapsing it to O(n). Dynamic programming (DP) is that idea made systematic: define subproblems, express each one through smaller ones, and solve every subproblem exactly once, in an order where its dependencies are already solved.
ML context.
- Sequence alignment and similarity: edit distance and longest common subsequence (lessons 12.11–12.12, 12.15) for fuzzy matching, evaluation metrics like word error rate, and dynamic time warping.
- Decoding: the Viterbi algorithm finds the most likely tag sequence in HMMs and CRFs (lesson 12.16); CTC loss sums over alignments with a DP.
- Reinforcement learning: value iteration and the Bellman equation are DP over states.
- Planning under budgets: knapsack-style choices of features, models or batches (lesson 12.6).
1. The running problem: cheapest hops to the end
Task: you stand at index 0 of an array cost. From index i you may jump forward by 1, 2, …, k positions. Landing on index j
costs cost[j]. Return the minimum total cost to reach the last index.
best(i) = cheapest cost to reach the end from i = min over j in i + 1 … i + k of cost[j] + best(j). The recursion tree
branches k ways at every level, and the same positions are solved again and again.