Question Bank
Dynamic Programming Warm-Up
Difficulty: Easy
Memoization, tabulation, and writing transitions for classic 1D DP. Code stems are Python.
Dynamic Programming Warm-Up
Memoization, tabulation, and writing transitions for classic 1D DP. Code stems are Python.
Question Bank
Easy
Python
3 questions
dynamic-programming
memoization
fundamentals
quiz
426 views
12
Implement fib(n) two ways: top-down with memoization and bottom-up with tabulation. Compare their space cost.
Examples
Example 1:
Input: n = 10 (using both fib_memo and fib_tab)
Output: 55 from both versions
Explanation: Both are O(n) time. Memo uses O(n) space for the dict plus the recursion stack; tabulation uses O(n) for the array and O(1) stack. Dropping tabulation to O(1) by tracking only the last two values is a one-line tweak.What are the two ingredients that make a problem solvable by DP? Define each in one sentence.
Implement climb_stairs(n): how many ways to reach step n if you can step 1 or 2 at a time? Use O(1) space.
Examples
Example 1:
Input: n = 5
Output: 8
Explanation: f(n) = f(n - 1) + f(n - 2) with f(0) = f(1) = 1 (Fibonacci shifted by one). Sequence: f(0..5) = 1, 1, 2, 3, 5, 8. Roll only the last two scalars for O(1) space.