What this topic covers
18 subtopics- 1D DP5
- Coin change5
- Foundations4
- Knapsack4
- String DP4
- 2D DP3
- Interval DP3
- Subsequences3
- LCS2
- Memoisation2
- State machine DP2
- Tabulation2
Show all 18 subtopics
- Bitmask DP1
- Classic DP1
- Edit distance1
- Space optimisation1
- Subset sum1
- Unbounded knapsack1
- Beginner 15
- Intermediate 15
- Advanced 15
About this topic
Dynamic programming solves a problem by combining answers to overlapping subproblems, computing each one only once. The hard part is the state – what does dp[i] (or dp[i][j]) mean? – and the transition that builds it from smaller states. Top-down (memoised recursion) and bottom-up (tables) give the same answers. Many questions here show a partly filled table with one cell marked "?"; every value was computed by a checker program, often against a brute-force solution.
Free preview
Sample questions
Try each one first, then open the answer for the explanation and why the other options are wrong.
Which two properties make a problem suitable for dynamic programming?
Show answer and explanation
Explanation
Optimal substructure: the best answer is built from best answers to smaller problems. Overlapping subproblems: the same smaller problems recur, so storing them pays off. Merge sort has the first but not the second, so it is plain divide and conquer.
Why the other options are wrong
- BInput order is irrelevant.
- CThat describes greedy algorithms.
- DRandomness is unrelated.
What is the length of the longest common subsequence of ABCBDAB and BDCABA?
The answer is a number – work it out, then open the solution.
Show answer and explanation
Explanation
For example BCBA or BDAB. dp[i][j] = dp[i − 1][j − 1] + 1 if the characters match, else max(dp[i − 1][j], dp[i][j − 1]) – O(mn).
Matrices A (10 × 30), B (30 × 5) and C (5 × 60) are multiplied. What is the minimum number of scalar multiplications?
The answer is a number – work it out, then open the solution.
Show answer and explanation
Explanation
(AB)C costs 10·30·5 + 10·5·60 = 1500 + 3000 = 4500; A(BC) costs 30·5·60 + 10·30·60 = 27,000. Matrix-chain DP tries every split point k for every interval: O(n³).