Mock 5 — Dynamic Programming (60 min)

# Mock 5 — Dynamic Programming ## The brief Four DP problems, 60 minutes. The hardest category — practice deriving the state and recurrence under time pressure. ## Problem 1 — Climbing Stairs (Easy, ~10 min) Climb stairs. Each step: 1 or 2 stairs. How many distinct ways to reach the top? ### Solution ```python def climb_stairs(n): if n <= 2: return n a, b = 1, 2 for _ in range(n - 2): a, b = b, a + b return b ``` State: ways to reach step i. Recurrence: ways(i) = ways(i-1) + ways(i-2). Fibonacci. ## Problem 2 — Coin Change (Medium, ~15 min) Given coins of different denominations and an amount, return the fewest coins needed to make that amount. Return -1 if impossible. ### Solution ```python def coin_change(coins, amount): dp = [float('inf')] * (amount + 1) dp[0] = 0 for i in range(1, amount + 1): for c in coins: if c <= i: dp[i] = min(dp[i], dp[i - c] + 1) return dp[amount] if dp[amount] != float('inf') else -1 ``` State: dp[i] = min coins for amount i. Recurrence: min over coins of dp[i-c] + 1. ## Problem 3 — Longest Increasing Subsequence (Medium, ~15 min) Find the length of the longest strictly increasing subsequence. ``` [10, 9, 2, 5, 3, 7, 101, 18] → 4 (e.g., [2, 3, 7, 101]) ``` ### Solution (O(N²)) ```python def length_of_lis(nums): n = len(nums) dp = [1] * n for i in range(n): for j in range(i): if nums[j] < nums[i]: dp[i] = max(dp[i], dp[j] + 1) return max(dp) ``` State: dp[i] = length of LIS ending at index i. Recurrence: 1 + max over compatible predecessors. ### O(N log N) variant (patience sorting) ```python from bisect import bisect_left def length_of_lis_fast(nums): tails = [] for x in nums: i = bisect_left(tails, x) if i == len(tails): tails.append(x) else: tails[i] = x return len(tails) ``` Trickier but faster. Mention it; code if time permits. ## Problem 4 — Word Break (Medium, ~20 min) Given a string `s` and a dictionary `wordDict`, return True if `s` can be segmented into a space-separated sequence of dictionary words. ``` s = "leetcode", wordDict = ["leet", "code"] → True s = "applepenapple", wordDict = ["apple", "pen"] → True ``` ### Solution ```python def word_break(s, word_dict): word_set = set(word_dict) n = len(s) dp = [False] * (n + 1) dp[0] = True for i in range(1, n + 1): for j in range(i): if dp[j] and s[j:i] in word_set: dp[i] = True break return dp[n] ``` State: dp[i] = True if s[:i] can be segmented. Recurrence: dp[i] = any j where dp[j] is True and s[j:i] is in dict. Convert wordDict to set for O(1) lookup. ## Self-rubric - [ ] All 4 solved correctly - [ ] Derived the state and recurrence BEFORE coding for each - [ ] Climb Stairs: O(1) space variant - [ ] LIS: at least the O(N²) DP; bonus for O(N log N) - [ ] Word Break: O(N²) time - [ ] Could articulate the meaning of dp[i] for each problem in one sentence ## Deliverables - Solutions. - For each problem, a one-sentence statement of the state: "dp[i] = X." - Note any problem you couldn't solve in time; circle back later.