Unit 3: Trees & Dynamic Programming
Dynamic Programming Fundamentals
18 min read · 30% complete
Explanation
Dynamic Programming means: solve a problem once, write the answer down, and reuse it instead of computing it again.
It works when a big problem is made of smaller problems that repeat, like Fibonacci numbers.
Key exam points
- Needs optimal substructure + overlapping subproblems
- Memoisation (top-down) vs tabulation (bottom-up)
- Knapsack O(nW) is pseudo-polynomial, not polynomial
Previous year questions
Solve the 0/1 Knapsack problem using dynamic programming for the given instance.
2024 · 10 marks
Differentiate between greedy method and dynamic programming with examples.
2023 · 6 marks
Practice quiz
0/1 Knapsack DP runs in:
Memoisation is a: