This Java program computes the Fibonacci sequence using dynamic programming. The Fibonacci sequence is defined by the recurrence relation:
F(n) = F(n-1) + F(n-2) with base cases F(0) = 0 and F(1) = 1.
Java Program
public class FibonacciDP {
// Function to compute the Fibonacci sequence using dynamic programming
public static int fibonacci(int n) {
if (n == 0) {
return 0;
} else if (n == 1) {
return 1;
}
// DP array to store Fibonacci numbers up to F(n)
int[] dp = new int[n + 1];
// Base cases
dp[0] = 0;
dp[1] = 1;
// Build the Fibonacci sequence from the bottom up
for (int i = 2; i <= n; i++) {
dp[i] = dp[i – 1] + dp[i – 2];
}
// Return the nth Fibonacci number
return dp[n];
}
public static void main(String[] args) {
int n = 10; // Example: Find the 10th Fibonacci number
// Compute and print the Fibonacci number
int result = fibonacci(n);
System.out.println(“The ” + n + “th Fibonacci number is: ” + result);
}
}
Explanation of the Program Structure
This program computes the Fibonacci sequence using dynamic programming. Dynamic programming allows us to store the results of subproblems, avoiding the exponential time complexity of the naive recursive solution.
- fibonacci function: This function computes the nth Fibonacci number using dynamic programming. It takes an integer
nas input and returnsF(n). The function uses a DP array to store the Fibonacci numbers calculated so far, allowing the program to reuse previously computed values. - Dynamic Programming Array (dp): The DP array
dp[i]stores the ith Fibonacci number. The array is built from the bottom up, starting with the base casesdp[0] = 0anddp[1] = 1. For eachifrom 2 ton, the Fibonacci number is calculated asdp[i] = dp[i-1] + dp[i-2]. - Main logic: The program initializes the base cases for
F(0)andF(1)and then computes each Fibonacci number up toF(n)using the recursive relation. Once the array is fully populated, the value atdp[n]is returned, which is the nth Fibonacci number. - Base cases: The base cases are handled separately. If
nis 0 or 1, the function directly returnsF(0)orF(1). - main function: This function initializes a sample value of
n(in this case, 10) and calls thefibonaccifunction to compute the 10th Fibonacci number. The result is then printed to the console.
Step-by-Step Process:
- We initialize a DP array of size
n + 1to store the Fibonacci numbers from 0 ton. - We set the base cases:
dp[0] = 0anddp[1] = 1. - We iterate from
i = 2tonand compute each Fibonacci number using the relationdp[i] = dp[i-1] + dp[i-2]. - The final result is stored in
dp[n], which is the nth Fibonacci number.
Example:
Consider finding the 10th Fibonacci number. The program will calculate the following sequence:
F(0) = 0, F(1) = 1, F(2) = 1, F(3) = 2, F(4) = 3, F(5) = 5,
F(6) = 8, F(7) = 13, F(8) = 21, F(9) = 34, F(10) = 55
The program will output:
The 10th Fibonacci number is: 55
Conclusion:
This Java program efficiently computes the Fibonacci sequence using dynamic programming. The time complexity of this solution is O(n), where n is the input number. This approach is far more efficient than the naive recursive solution, which has exponential time complexity. By storing the results of subproblems, we avoid redundant calculations and significantly improve performance.
