Fibonacci Using DP in DSA C - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is the main idea behind using Dynamic Programming (DP) to calculate Fibonacci numbers?

DP stores the results of smaller subproblems (previous Fibonacci numbers) to avoid repeated calculations, making the process faster and more efficient.

beginner

In Fibonacci DP, what does the 'memoization' technique mean?

Memoization means saving the results of Fibonacci calculations in a table (array) so that when the same value is needed again, it can be retrieved instantly instead of recalculating.

intermediate

What is the time complexity of calculating Fibonacci numbers using DP compared to the naive recursive method?

Using DP, the time complexity is O(n) because each Fibonacci number is calculated once. The naive recursive method has exponential time complexity O(2^n) due to repeated calculations.

intermediate

Why is the bottom-up approach often preferred over the top-down approach in Fibonacci DP?

Bottom-up builds the solution from the smallest subproblems up, using iteration and no recursion, which avoids function call overhead and stack issues, making it more efficient in practice.

beginner

Show the base cases used in Fibonacci DP and explain why they are important.

Base cases: fib(0) = 0 and fib(1) = 1. They are important because they stop the recursion or iteration and provide starting values to build the rest of the Fibonacci sequence.

What does DP store to optimize Fibonacci calculation?

A Prime numbers

B Random numbers

C Only the last Fibonacci number

D Previous Fibonacci numbers

DP stores previous Fibonacci numbers to avoid recalculating them.

What is the time complexity of Fibonacci using DP?

A O(n)

B O(n^2)

C O(2^n)

D O(log n)

DP calculates each Fibonacci number once, so time complexity is O(n).

Which approach uses iteration to build Fibonacci numbers from the bottom up?

A Divide and conquer

B Top-down

C Bottom-up

D Greedy

Bottom-up approach uses iteration starting from base cases.

What are the base cases for Fibonacci DP?

A fib(0)=0, fib(1)=1

B fib(1)=0, fib(2)=1

C fib(0)=1, fib(1)=1

D fib(2)=0, fib(3)=1

Base cases are fib(0)=0 and fib(1)=1 to start the sequence.

Memoization in Fibonacci DP means:

A Ignoring previous results

B Saving results to avoid repeated work

C Using random numbers

D Calculating recursively without storage

Memoization saves results to avoid recalculating the same Fibonacci numbers.

Explain how Dynamic Programming improves the calculation of Fibonacci numbers compared to simple recursion.

Think about how remembering past answers helps.

Describe the difference between top-down and bottom-up approaches in Fibonacci DP.

One starts from the problem and breaks down, the other builds up from the smallest cases.