Fibonacci Using DP in DSA Java - 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 using DP, what does the 'memoization' technique mean?

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

intermediate

Why is the DP approach better than the simple recursive approach for Fibonacci?

Because DP avoids repeated work by storing results, it reduces the time complexity from exponential (2^n) to linear (n), making it much faster for large numbers.

beginner

What is the time complexity of Fibonacci calculation using DP?

The time complexity is O(n) because each Fibonacci number up to n is calculated once and stored.

beginner

Show the base cases used in Fibonacci DP implementation.

The base cases are: Fibonacci(0) = 0 and Fibonacci(1) = 1. These are the starting points for building up the solution.

What does DP store to optimize Fibonacci calculation?

A No values, it recalculates every time

B Random numbers

C Only the last Fibonacci number

D Previously calculated Fibonacci numbers

DP stores previously calculated Fibonacci numbers to avoid repeated calculations.

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 Divide and conquer

B Memoization

C Brute force

D Backtracking

Memoization saves results of subproblems to avoid repeated work.

What are the base cases for Fibonacci DP?

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

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

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

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

The base cases are Fib(0)=0 and Fib(1)=1.

Why is DP preferred over simple recursion for Fibonacci?

A It avoids repeated calculations

B It uses more memory

C It is harder to implement

D It calculates Fibonacci numbers randomly

DP avoids repeated calculations by storing results, making it faster.

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 steps to implement Fibonacci using bottom-up Dynamic Programming.

Start from the smallest Fibonacci numbers and build up.

Practice

1. What is the main advantage of using Dynamic Programming (DP) to calculate Fibonacci numbers compared to a simple recursive approach?

easy

A. It uses less memory by not storing any intermediate results.

B. It avoids repeated calculations by storing results of subproblems.

C. It calculates Fibonacci numbers using a closed-form formula.

D. It uses randomization to speed up the calculation.

Solution

1. Step 1: Understand recursive Fibonacci drawbacks

   Simple recursion recalculates the same Fibonacci numbers many times, causing inefficiency.

2. Step 2: How DP improves calculation

   DP stores results of smaller Fibonacci numbers to reuse them, avoiding repeated work.

3. Final Answer:

   It avoids repeated calculations by storing results of subproblems. -> Option B

4. Quick Check:

   DP stores subproblem results = avoids repeats [OK]

Hint: DP saves previous results to avoid repeated work [OK]

Common Mistakes:

• Thinking DP uses less memory than recursion
• Confusing DP with closed-form formulas
• Believing DP uses randomization

2. Which of the following Java code snippets correctly initializes the DP array for Fibonacci calculation of size n?

easy

A. int[] dp = new int[n]; dp[0] = 0; dp[1] = 1;

B. int[] dp = new int[n]; dp[0] = 1; dp[1] = 1;

C. int[] dp = new int[n-1]; dp[0] = 0; dp[1] = 1;

D. int[] dp = new int[n+1]; dp[0] = 0; dp[1] = 1;

Solution

1. Step 1: Determine array size for Fibonacci DP

   To store Fibonacci numbers up to n, array size must be n+1 to include index n.

2. Step 2: Check base cases initialization

   Fibonacci starts with dp[0] = 0 and dp[1] = 1, so these must be set correctly.

3. Final Answer:

   int[] dp = new int[n+1]; dp[0] = 0; dp[1] = 1; -> Option D

4. Quick Check:

   Array size n+1 with dp[0]=0, dp[1]=1 = correct initialization [OK]

Hint: Array size must be n+1 to hold Fibonacci up to n [OK]

Common Mistakes:

• Using array size n instead of n+1
• Initializing dp[0] as 1 instead of 0
• Using array size n-1 causing index errors

3. What is the output of the following Java code snippet?

int n = 5;
int[] dp = new int[n+1];
dp[0] = 0;
dp[1] = 1;
for (int i = 2; i <= n; i++) {
    dp[i] = dp[i-1] + dp[i-2];
}
System.out.println(dp[n]);

medium

A. 3

B. 8

C. 5

D. 13

Solution

1. Step 1: Calculate Fibonacci values up to n=5

   dp[0]=0, dp[1]=1 Then dp[2]=1, dp[3]=2, dp[4]=3, dp[5]=5

2. Step 2: Output dp[5]

   The value at dp[5] is 5, so the output is 5.

3. Final Answer:

   5 -> Option C

4. Quick Check:

   Fibonacci(5) = 5 [OK]

Hint: Fibonacci(5) is 5 by definition [OK]

Common Mistakes:

• Confusing index with Fibonacci value
• Calculating dp[5] as 8 (Fibonacci(6))
• Off-by-one errors in loop

4. Identify the error in the following Java code for Fibonacci using DP and select the correct fix:

int n = 6;
int[] dp = new int[n];
dp[0] = 0;
dp[1] = 1;
for (int i = 2; i <= n; i++) {
    dp[i] = dp[i-1] + dp[i-2];
}
System.out.println(dp[n]);

medium

A. Change array size to n+1 to avoid index out of bounds error.

B. Initialize dp[2] = 1 before the loop.

C. Change loop condition to i < n instead of i <= n.

D. Remove dp[0] initialization.

Solution

1. Step 1: Analyze array size and loop bounds

   Array dp has size n (6), but loop runs i from 2 to 6 inclusive, accessing dp[6] which is out of bounds.

2. Step 2: Fix array size to n+1

   Increasing array size to n+1 (7) allows dp[6] access without error.

3. Final Answer:

   Change array size to n+1 to avoid index out of bounds error. -> Option A

4. Quick Check:

   Array size n+1 fixes index error [OK]

Hint: Array size must cover max index used in loop [OK]

Common Mistakes:

• Ignoring index out of bounds exception
• Changing loop condition without fixing array size
• Unnecessary initialization of dp[2]

5. You want to calculate the 10th Fibonacci number using DP but with space optimization to use only two variables instead of an array. Which code snippet correctly implements this?

hard

A. int a = 0, b = 1, c = 0; for (int i = 2; i <= 10; i++) { c = a + b; a = b; b = c; } System.out.println(c);

B. int a = 0, b = 1; for (int i = 2; i <= 10; i++) { a = a + b; b = a; } System.out.println(b);

C. int a = 0, b = 1; for (int i = 2; i < 10; i++) { int c = a + b; a = b; b = c; } System.out.println(b);

D. int a = 1, b = 1; for (int i = 2; i <= 10; i++) { int c = a + b; a = b; b = c; } System.out.println(b);

Solution

1. Step 1: Understand space optimization for Fibonacci

   We only need last two Fibonacci numbers to calculate the next, so two variables plus one temp variable suffice.

2. Step 2: Check loop and initialization correctness

   Start with a=0, b=1 (F0 and F1), loop from 2 to 10 inclusive, update c = a+b, then shift a=b, b=c.

3. Step 3: Verify output

   After loop, c holds Fibonacci(10) = 55, which is printed.

4. Final Answer:

   int a = 0, b = 1, c = 0; for (int i = 2; i <= 10; i++) { c = a + b; a = b; b = c; } System.out.println(c); -> Option A

5. Quick Check:

   Two vars + temp, correct loop = Fibonacci(10) [OK]

Hint: Use two vars and update in loop to save space [OK]

Common Mistakes:

• Incorrect loop bounds causing off-by-one
• Wrong initial values for a and b
• Not updating variables in correct order