Fibonacci with DP in Java: Explanation & Practice

Calculate nth Fibonacci number efficiently

Problem summary

Calculate the nth Fibonacci number using dynamic programming. This is the gateway problem to understanding DP - storing solutions to avoid recomputation.

Starter code

public class Main {
    public static void main(String[] args) {
        int n = 10;
        
        // dp[i] = dp[i-1] + dp[i-2]
        // Base: dp[0]=0, dp[1]=1
        // Print: Fibonacci: 55
    }
}

Expected output and test cases

F(10) = 55
```
Fibonacci: 55
```
F(7) = 13
```
Fibonacci: 13
```
F(2) = 1
```
Fibonacci: 1
```

Hints

Create array dp of size n+1
dp[0]=0, dp[1]=1 are base cases
For i from 2 to n: dp[i] = dp[i-1] + dp[i-2]
Can optimize to O(1) space by keeping only last two values

Related Data Structures & Algorithms exercises

Practice Longest Repeating Character Replacement in Java
Practice Fruit Into Baskets in Java
Practice Climbing Stairs in Java

Practice all Data Structures & Algorithms exercises · Run this idea in the Java compiler