The Fibonacci sequence is defined as F(n) = F(n-1) + F(n-2) with base cases F(0)=1 and F(1)=1. A naive recursive solution recalculates many subproblems, leading to exponential time. By storing results in a DP array, we avoid recomputation and compute the result efficiently.

Approach:

Initialize a DP array dp of size n+1 with -1 to store results.
Set the base cases: dp[0] = 1, dp[1] = 1.
Iterate from i = 2 to n and compute dp[i] = dp[i-1] + dp[i-2].
Return dp[n] as the answer.

Code

#include <bits/stdc++.h>
using namespace std;

int main() {
    // Number for which Fibonacci is to be calculated
    int n = 3;

    // Create a dp array initialized with -1
    vector<int> dp(n + 1, -1);

    // Base cases
    dp[0] = 1;
    dp[1] = 1;

    // Fill dp array using bottom-up dynamic programming
    for (int i = 2; i <= n; i++) {
        dp[i] = dp[i - 1] + dp[i - 2];
    }

    // Print the nth Fibonacci number
    cout << dp[n];
    return 0;
}