Sign in to watch this lesson
Algorithms - Dynamic Programming · 4:06
Classic 1D DP
Give the Fibonacci recurrence real choices and the classic one-dimensional DPs appear: ways to climb stairs with strides of 1, 2 or 3 (274 ways to the tenth step), the fewest coins from {1, 5, 6, 9} to pay 11 (5 + 6, where greedy's 9 + 1 + 1 needs three), and counting payments, where putting coins in the outer loop counts 6 sets while putting amounts outside counts 22 ordered sequences. We finish with the take-or-skip house robber (18 from 5 1 3 9 2 4, beating both alternating picks) and its trading cousin, weighted interval scheduling.
You will learn
- Write ways[i] = sum of ways[i - s] for stairs and dice sums, and bound it by O(n * |S|).
- Solve minimum coin change with dp[x] = 1 + min dp[x - c], a safe finite infinity, and reconstruction by storing the winning coin; explain why greedy fails for non-canonical coin systems.
- Predict whether a counting DP counts combinations or ordered sequences from its loop order, and apply the modulus after every addition.
- Model take-or-skip problems such as the house robber with dp[i] = max(dp[i-1], dp[i-2] + a_i), and extend the idea to weighted interval scheduling.