Fibonacci is a degenerate dynamic-programming problem: no decision, just a sum. More complicated DP problems look back further and involve comparison operations.
Claims
Fibonacci is a degenerate dynamic-programming problem: no decision, just a sum. More complicated DP problems look back further and involve comparison operations.
Fibonacci is like a bike — two wheels, no choices, you just pedal. Coin change is like a Lamborghini — same category (it goes), but every step involves a choice (min over coins) and the lookback set is arbitrary. Between bike and Lamborghini sits a graded family of DP problems, each one modification away from Fibonacci:
| Problem | Modification | What it adds |
|---|---|---|
| Climbing Stairs | none (relabeled) | counting interpretation of the same recurrence |
| Tribonacci | window → 3 | longer lookback |
| House Robber | add max() | first optimization choice |
| Min Cost Climbing Stairs | min() + per-step cost | optimization + per-element input |
| Maximum Subarray (Kadane) | max(nums[i], F(i-1)+nums[i]) | extend-or-restart choice |
| Decode Ways | conditional contributions | gated recurrence terms |
| Unique Paths | 2D state | promote state to a grid |
| Coin Change (min coins) | arbitrary lookback + min() | all of the above together |
Working the family in order is a constructive way to learn DP: each problem adds one feature — a comparison, a longer window, a per-step value, an extra dimension. By Coin Change you’ve internalized memoization, optimization, variable lookback, and multi-dimensional state without ever facing them all at once.