171: DSA - Greedy, Backtracking, and Dynamic Programming
Learning outcomes
- identify overlapping subproblems and state;
- prove or challenge a greedy choice;
- bound backtracking with pruning.
Practice
Solve interval scheduling greedily, generate subsets with backtracking, and solve climbing stairs and coin change with memoization and tabulation. Write the recurrence and base cases before code.
Lesson and worked examples
Interval scheduling sorts by earliest finish time, then accepts an interval when its start is at least the last finish. The exchange argument is that an optimal schedule can replace its first choice with the earliest-finishing interval without reducing remaining room. For [1,3], [2,4], [3,5], choose the first and third.
Backtracking for subsets chooses include/exclude, records at a leaf, and undoes mutable state. With [a,b], leaves are [], [b], [a], [a,b] (ordering is a contract). Climbing stairs has dp[i] = dp[i-1] + dp[i-2], while coin change minimizes 1 + dp[amount - coin]; initialize unreachable amounts to infinity, not zero.
Tests and rubric
Test zero/one stair, unreachable and zero coin-change targets, duplicate coins, empty candidates, duplicate subset values, overlapping and touching intervals, and unsorted intervals. Score 3 points each for state/recurrence, base cases, proof or pruning, complexity, and edge tests. A greedy answer without an exchange argument is incomplete.
Checkpoint
Explain why greedy needs an exchange argument, what the DP state means, and how a missing base case manifests.
Decision test
For every DP solution, name the state, transition, base case, and evaluation order. For backtracking, name the choice, undo step, and pruning rule. For greedy, give a reason a locally chosen item can replace part of an optimal solution. If you cannot state that argument, the implementation may be a pattern imitation rather than a solution.