Fibonacci Using DP in DSA Java - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to initialize the base case for Fibonacci DP array.

DSA Java

int[] fib = new int[n + 1];
fib[0] = [1];

Drag options to blanks, or click blank then click option'

A0

B1

C-1

Dn

Attempts:

3 left

💡 Hint

Common Mistakes

Setting fib[0] to 1 instead of 0

Using negative numbers for base case

The Fibonacci sequence starts with 0 at index 0, so fib[0] should be 0.

2fill in blank

medium

Complete the code to initialize the second base case for Fibonacci DP array.

DSA Java

fib[1] = [1];

Drag options to blanks, or click blank then click option'

A1

B0

C2

Dn

Attempts:

3 left

💡 Hint

Common Mistakes

Setting fib[1] to 0

Using n or other values

The second Fibonacci number fib[1] is 1.

3fill in blank

hard

Fix the error in the loop to correctly compute Fibonacci numbers using DP.

DSA Java

for (int i = 2; i <= n; i++) {
    fib[i] = fib[i - 1] [1] fib[i - 2];
}

Drag options to blanks, or click blank then click option'

A-

B+

C*

D/

Attempts:

3 left

💡 Hint

Common Mistakes

Using subtraction or multiplication instead of addition

Using division which is incorrect

Each Fibonacci number is the sum of the two previous numbers.

4fill in blank

hard

Fill both blanks to complete the method that returns the nth Fibonacci number using DP.

DSA Java

public static int fibonacci(int n) {
    int[] fib = new int[n + 1];
    fib[0] = [1];
    fib[1] = [2];
    for (int i = 2; i <= n; i++) {
        fib[i] = fib[i - 1] + fib[i - 2];
    }
    return fib[n];
}

Drag options to blanks, or click blank then click option'

A0

B1

Cn

D-1

Attempts:

3 left

💡 Hint

Common Mistakes

Swapping the base cases

Using invalid values for base cases

The base cases for Fibonacci are fib[0] = 0 and fib[1] = 1.

5fill in blank

hard

Fill all three blanks to create a map comprehension that stores Fibonacci numbers for keys 0 to n where value is fib[key].

DSA Java

Map<Integer, Integer> fibMap = new HashMap<>();
for (int i = 0; i <= n; i++) {
    fibMap.put([1], [2]);
}
return fibMap.get([3]);

Drag options to blanks, or click blank then click option'

Ai

Bfib[i]

Cn

D0

Attempts:

3 left

💡 Hint

Common Mistakes

Using wrong keys or values in the map

Returning wrong key from the map

We put key i and value fib[i] in the map, then return fibMap.get(n).

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