Question 1

What specifically qualifies naive recursive Fibonacci as a dynamic programming problem, according to the module's definition?

Accepted Answer

It exhibits overlapping subproblems — the same smaller input (like `fib(3)`) is recomputed independently and repeatedly across different, unrelated branches of the recursive call tree, rather than each distinct input being computed only once. — The module explicitly defines "overlapping subproblems" as the defining feature that makes a problem suited to dynamic programming — the same smaller input, like `fib(3)`, gets recomputed from scratch multiple times across different, independent branches of the call tree (once via the `fib(4)` branch, once via the `fib(3)` branch directly), rather than each unique input being resolved exactly once. This repeated, wasted recomputation is precisely what memoization and tabulation both eliminate. Option A overgeneralizes — plenty of recursive functions (like Module P-1's `factorial`) have no overlapping subproblems at all, since each call is for a genuinely distinct input, and gain nothing from memoization. Option C is a fabricated and nonsensical criterion based on operator usage rather than the actual recursive call structure. Option D is false — having a base case is a requirement for any correct recursive function (Module P-1), not something specific to or sufficient for identifying a dynamic programming problem.

Question 2

In `fibMemo`, what does the line `if (cache.has(n)) return cache.get(n)!;` actually prevent, and why is this the mechanism that changes the complexity from O(2ⁿ) to O(n)?

Accepted Answer

It prevents the function from recursing further into `fibMemo(n - 1)` and `fibMemo(n - 2)` whenever the answer for this specific `n` has already been computed and stored in a prior call (from any branch of the recursion) — since every distinct value of `n` triggers this shortcut after its very first computation, each distinct subproblem ends up being fully computed exactly once across the entire execution, rather than potentially many times. — This check is the entire mechanism behind the complexity improvement: the first time `fibMemo` is called with a particular `n`, it computes the result and stores it in `cache`. Every subsequent call with that same `n` — regardless of which branch of the recursion it comes from — hits this check and returns immediately, in O(1), without triggering any further recursive calls. Since there are only n distinct possible values of `n` from 1 up to the original input, and each is computed at most once, the total work across the entire call tree is bounded by O(n), not the O(2ⁿ) of the unmemoized version. Option A is a fabricated and irrelevant claim about negative-number handling, unrelated to what this line does. Option C misdescribes the code — `fibMemo` still recurses via `fibMemo(n - 1, cache)` and `fibMemo(n - 2, cache)` when the cache doesn't already have an answer; this is explicitly top-down (still recursive), not iterative, as the module states directly. Option D directly contradicts the module's explicit claim that this change collapses the complexity class from O(2ⁿ) to O(n), which is a complexity-class change, not merely a constant-factor improvement.

Question 3

Why is `fibConstantSpace` able to achieve O(1) space, while `fibTabulation` (the full-table version) uses O(n) space, even though both compute the exact same result in O(n) time?

Accepted Answer

Because each value in the Fibonacci sequence only ever depends on the two values immediately preceding it — not the entire history of previously computed values — only those two most recent values need to be kept in memory at any point, rather than retaining the full table of every value computed so far. — The module explains this directly: since `table[i] = table[i-1] + table[i-2]` only ever looks back two positions, there's no need to retain the entire table of previously computed values — just the two most recent ones (`prev1`, `prev2`), updated in place on each iteration. This drops the memory requirement from an array sized to the input (O(n)) down to a fixed, constant number of variables (O(1)), regardless of how large `n` grows. Option A is false — the module presents `fibConstantSpace` as a correct, equivalent optimization, computing identical results to the tabulated version. Option C is backwards and factually incorrect — `fibConstantSpace` explicitly uses a `for` loop, not recursion; it is `fibMemo` that uses recursion, and recursion (Module P-1) generally costs more stack space, not less. Option D directly contradicts the module's explicit claim that this specific optimization achieves O(1) space, distinct from the O(n) space of the full-table version.

Module P-11 — Dynamic Programming I: Memoization and Tabulation

Where the Waste Comes From

Memoization: Remember, Then Check Before Recomputing

Tabulation: Build the Answer Bottom-Up, No Recursion at All

Climbing Stairs: The Same Three-Step Progression, Applied Fresh

Compressing Space: You Often Don't Need the Whole Table

Where This Shows Up in Your Stack

Summary

Test your knowledge with more question sets

Sign in to keep reading

Discussion