Fibonacci Using DP in DSA Typescript - 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 efficient.

beginner

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

Memoization means saving the result of each Fibonacci number once calculated, so if we need it again, we just reuse it instead of recalculating.

intermediate

What is the time complexity of Fibonacci calculation using DP?

The time complexity is O(n) because each Fibonacci number from 0 to n is calculated once and stored for reuse.

beginner

Why is the simple recursive Fibonacci approach inefficient compared to DP?

Simple recursion recalculates the same Fibonacci numbers many times, causing exponential time complexity, while DP avoids this by storing results.

beginner

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

Base cases are Fib(0) = 0 and Fib(1) = 1. They stop the recursion and provide starting points to build all other Fibonacci numbers.

What does DP store to optimize Fibonacci calculation?

A Previously calculated Fibonacci numbers

B Random numbers

C Only the last Fibonacci number

D No values, it recalculates every time

DP stores all previously calculated Fibonacci numbers to avoid repeated work.

What is the time complexity of Fibonacci using DP?

A O(n)

B O(2^n)

C O(log n)

D O(n^2)

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

Which technique is used in DP to save results of subproblems?

A Greedy

B Backtracking

C Memoization

D Brute force

Memoization saves results to avoid repeated calculations.

What are the base cases for Fibonacci DP?

A Fib(1) = 1 and Fib(2) = 2

B Fib(0) = 0 and Fib(1) = 1

C Fib(0) = 1 and Fib(1) = 1

D Fib(2) = 1 and Fib(3) = 2

Base cases start the sequence correctly with Fib(0) = 0 and Fib(1) = 1.

Why is simple recursion inefficient for Fibonacci?

A It only works for small numbers

B It uses too much memory

C It does not return correct results

D It recalculates the same values many times

Simple recursion repeats calculations, causing exponential time.

Explain how Dynamic Programming improves Fibonacci number calculation compared to simple recursion.

Think about how saving answers helps avoid doing the same work twice.

Describe the role of base cases in the Fibonacci DP approach and why they are necessary.

Base cases are like the first steps in a staircase you need to climb.