Algorithms Dynamic Programming & Optimization 1 — Questions and Answers
Question 1: What are the two key properties a problem must have to be solvable with dynamic programming?
- Linearity and monotonicity
- Optimal substructure and overlapping subproblems (Correct answer)
- Greedy choice and independence
- Recursion and memoization
Correct answer: Optimal substructure and overlapping subproblems
Dynamic programming applies when a problem has optimal substructure (optimal solution built from optimal sub-solutions) and overlapping subproblems (same subproblems recur).
Question 2: What is the time complexity of the classic 0/1 Knapsack DP solution with n items and capacity W?
- O(n + W)
- O(n log W)
- O(nW) (Correct answer)
- O(n²)
Correct answer: O(nW)
The 0/1 Knapsack DP fills an n×W table where each cell takes O(1) time, giving O(nW) overall complexity.
Question 3: Which DP problem asks for the length of the longest subsequence common to two strings?
- Longest Increasing Subsequence
- Edit Distance
- Longest Common Subsequence (Correct answer)
- Coin Change
Correct answer: Longest Common Subsequence
The Longest Common Subsequence (LCS) problem finds the longest sequence present in both strings in the same order, solved in O(mn) by DP.
Question 4: What is memoization in the context of dynamic programming?
- Sorting subproblems before solving
- Caching results of subproblems to avoid redundant computation (Correct answer)
- Converting recursion to iteration
- Splitting the problem into independent parts
Correct answer: Caching results of subproblems to avoid redundant computation
Memoization stores the result of each subproblem the first time it is solved so future calls return the cached answer immediately.
Question 5: In the Fibonacci sequence computed with DP, what is the time complexity compared to naive recursion?
- Both are O(2ⁿ)
- DP is O(n) vs naive O(2ⁿ) (Correct answer)
- DP is O(n²) vs naive O(n)
- Both are O(n)
Correct answer: DP is O(n) vs naive O(2ⁿ)
Naive recursive Fibonacci recomputes subproblems exponentially (O(2ⁿ)), while DP computes each of the n values exactly once in O(n) time.
Question 6: What approach does the Coin Change problem use to find the minimum number of coins for a target amount?
- Greedy selection of largest coin
- Bottom-up DP filling amounts from 0 to target (Correct answer)
- Binary search on coin values
- Divide and conquer on coin denominations
Correct answer: Bottom-up DP filling amounts from 0 to target
The DP approach builds a table where each entry stores the minimum coins needed for that amount, using previously computed smaller amounts.
Algorithms Dynamic Programming & Optimization 1
What are the two key properties a problem must have to be solvable with dynamic programming?