Which of the following problems is the best candidate for dynamic programming?
AMerge sort on an array of integers
BBinary search on a sorted array
CComputing the minimum number of coins to make change for a given amount
DFinding the maximum element in an unsorted array
Coin change has both required DP properties: optimal substructure (the minimum coins for amount n uses minimum coins for smaller amounts) and overlapping subproblems (the same sub-amounts are computed repeatedly in naive recursion). Merge sort and binary search use divide-and-conquer with non-overlapping subproblems. Finding the maximum element requires a single linear scan with no subproblem reuse.
Question 2 True / False
Top-down memoization and bottom-up tabulation always produce the same asymptotic time complexity for a given DP problem.
TTrue
FFalse
Answer: True
Both approaches solve each distinct subproblem exactly once. Asymptotic time complexity depends on the number of distinct subproblems times the cost per subproblem — the same quantity regardless of direction. They can differ in practice (stack overhead, whether all subproblems are computed) but not in asymptotic time complexity.
Question 3 Short Answer
Before writing any code for a DP problem, what should you define first, and why is this step considered the hardest part?
Think about your answer, then reveal below.
Model answer: You should precisely define what dp[i] (or dp[i][j], etc.) represents — which subproblem it solves and what its value encodes. This is the hardest step because a vague or incorrect subproblem definition leads to a recurrence that is wrong or cannot be computed, even if the implementation mechanics are correct.
Many DP bugs originate from an ambiguous subproblem definition rather than a wrong recurrence formula. For coin change, dp[i] = 'minimum coins to make amount i' is precise and leads directly to dp[i] = min over all coins c of (1 + dp[i - c]). Without a clear definition first, the recurrence is guesswork that may fail on edge cases.