Fibonacci Number
Logical Breakdown
- [ ] Subproblem Identification:
- [ ] Optimal Substructure:
- [ ] Constraint Handling: (e.g., Modulo \(10^9 + 7\))
- [ ] Optimization: (Matrix Exponentiation if 'A' is huge)
Mathematical Rigor
State Definition
Let \(dp[i]\) be the state for the \(i\)-th subproblem.
Recurrence Relation
Visualization
Complexity Analysis
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Iterative DP | \(O(N)\) | \(O(1)\) |
Code Reference
package com.dsa.dynamic_programming;
import java.util.*;
/
* Problem: Fibonacci Number
* Group: 11. Dynamic Programming
*/
/
* ============================================================================================
* PROBLEM: Fibonacci Number
* ============================================================================================
*
* ---------------------
* 1. Problem Description
* ---------------------
* The Fibonacci numbers are a sequence where each number is the sum of the two preceding ones,
* starting from 0 and 1.
*
* Definition:
* F(0) = 0
* F(1) = 1
* F(N) = F(N - 1) + F(N - 2), for N > 1.
*
* Task: Given an integer A, calculate the Ath Fibonacci number.
*
* ---------------------
* 2. Logical Breakdown & Mathematical Formulation
* ---------------------
* Naive Recursion:
* Simply returning solve(A-1) + solve(A-2) results in recalculating the same states repeatedly.
* Time Complexity: O(1.618^A) -> Exponential (Too slow for A > 40).
*
* Dynamic Programming (Iterative):
* Instead of recursion, we build the solution from the bottom up.
* Let dp[i] be the i-th Fibonacci number.
* dp[0] = 0
* dp[1] = 1
* dp[i] = dp[i-1] + dp[i-2]
*
* Space Optimization:
* Notice that to calculate dp[i], we ONLY need the immediate previous two values:
* dp[i-1] and dp[i-2].
* We do not need the entire array.
* We can maintain two variables, a (representing i-2) and b (representing i-1).
*
* Algorithm:
* 1. Initialize a = 0, b = 1.
* 2. Loop from 2 to A:
* next = a + b
* a = b
* b = next
* 3. Return b (or a if A=0).
*
* ---------------------
* 3. Constraints & Complexity Analysis
* ---------------------
* Constraints:
* 0 <= A <= 40 (Result fits within a standard 32-bit Integer).
* If A > 46, we would need long to avoid overflow.
*
* Time Complexity:
* O(A) - We iterate linearly from 2 to A.
*
* Space Complexity:
* O(1) - We only store two integer variables, regardless of input size.
*
* Advanced Note:
* For extremely large A (e.g., A = 10^9), an O(log A) solution exists using Matrix Exponentiation.
* [[1, 1], [1, 0]]^A.
*
* ---------------------
* 4. Input / Output Format
* ---------------------
* Input: Integer A.
* Output: Integer denoting F(A).
*
* ---------------------
* 5. Examples
* ---------------------
* Input: A = 2
* Calculation: F(0)=0, F(1)=1 -> F(2) = 0+1 = 1.
* Output: 1
*
* Input: A = 9
* Sequence: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34
* Output: 34
*
* ============================================================================================
*/
public class FibonacciNumber {
public int solve(int A) {
// TODO: Implement solution
return 0;
}
public int fib(int i) {
return 0;
}
}