Avoiding repeated subproblem expansion
Naive Fibonacci recursion expands the same smaller indexes along many branches. Memoization stores a completed result by index and reuses it rather than expanding another identical computation tree.
The state key must capture what determines the result. Omitting a remaining budget or another relevant constraint can incorrectly merge different problems. Correct dynamic programming starts with a sufficient subproblem definition, not merely a table added to arbitrary recursion.
References: [1]
Top-down and bottom-up evaluation
Top-down memoization computes demanded states through calls; bottom-up tabulation orders states so prerequisites are already available. Fibonacci values can be computed sequentially from the preceding two, implementing the same recurrence without recursion.
Memoization alone does not resolve cyclic dependencies. A shortest-path recurrence indexed only by vertex can recurse around a cycle. Adding a bound on the number of edges creates layered dependencies, trading more states for a well-founded evaluation order.
References: [1]
Counting states and transition work
Count the distinct states and the candidate transitions examined at each. Reusing answers can remove repetition while leaving exponentially many states. Dynamic programming is therefore a design technique rather than a universal polynomial-time guarantee.
Fibonacci storage can keep only the preceding two values, while reconstructing a chosen solution may require additional decisions. Linear arithmetic counts and a constant number of stored values do not mean constant bit costs when the integers themselves grow.