50 lines (27 loc) · 2.29 KB

Practice Questions & Solutions — Dynamic Programming

📝

Practice set — covers SL No 70–71 (memoization, tabulation & the two DP conditions). Answer each from memory before opening the solution.

Q1. What two conditions must a problem satisfy to be solvable with dynamic programming?

💡 Solution & explanation

Answer: Optimal substructure (the optimal solution is built from optimal solutions of sub-problems) and overlapping sub-problems (the same sub-problems recur many times).

Explanation: If sub-problems don't overlap, plain divide & conquer suffices; DP's payoff comes from reusing repeated sub-problem results.

Q2. What is the difference between memoization and tabulation?

💡 Solution & explanation

Answer: Memoization is top-down: recurse naturally and cache each result (e.g. in a dict) so it's computed once. Tabulation is bottom-up: iteratively fill a table from the smallest sub-problems up to the answer.

Explanation: Memoization is easy to add to a recursive solution; tabulation avoids recursion overhead and can be more space-efficient.

Q3. Naive recursive Fibonacci is `O(2ⁿ)`. How does DP make it linear?

💡 Solution & explanation

Answer: By caching each fib(n) the first time it's computed, every value is calculated once, turning O(2ⁿ) into O(n) time.
```
from functools import lru_cache
@lru_cache(maxsize=None)
def fib(n):
    return n if n < 2 else fib(n - 1) + fib(n - 2)
```
Explanation: The naive version recomputes the same fib values exponentially often (overlapping sub-problems). Caching removes that redundant work; @lru_cache is built-in memoization.

Q4. Give the typical space trade-off difference between memoization and tabulation.

💡 Solution & explanation

Answer: Memoization uses the cache plus the recursion call stack (risking deep-recursion limits); tabulation uses an explicit table but no recursion stack, and can often be optimized to keep only the last few rows/values.

Explanation: For example, bottom-up Fibonacci can run in O(1) space by tracking just the previous two numbers — a common DP space optimization.