LeetCode 509: Fibonacci Number

Explanation:

• We can solve this problem using a simple iterative approach or a more optimized recursive approach with memoization.
• The recursive approach involves calculating Fibonacci numbers recursively, and we can use memoization to store the already computed values to avoid redundant calculations.
• We can create an array to store Fibonacci numbers up to n and then calculate the Fibonacci number for n using the previously computed values.
• Time Complexity: O(n) as we calculate each Fibonacci number only once.
• Space Complexity: O(n) for storing the Fibonacci numbers.

:

class Solution {
    public int fib(int n) {
        if (n <= 1) {
            return n;
        }
        int[] fibNums = new int[n + 1];
        fibNums[0] = 0;
        fibNums[1] = 1;
        for (int i = 2; i <= n; i++) {
            fibNums[i] = fibNums[i - 1] + fibNums[i - 2];
        }
        return fibNums[n];
    }
}