Dynamic Programming

Tabulation

• Bottom-Up Approach

• Solve all subproblems first and use them to build up the solution to the main problem.

• Typically involves filling up a DP table iteratively.

Memoisation

• Top-Down Approach

• Solve the problem recursively and store the result of each subproblem (usually using an array or map).

• Avoids recomputing already solved subproblems.

Fibonacci Using Dynamic Programming

The Fibonacci sequence is defined as:

f(n) = f(n-1) + f(n-2) With base cases: f(0) = 0, f(1) = 1

Naive Recursive Solution (Inefficient)

Copyint fibonacci(int n) {
    if (n <= 1) return n;
    return fibonacci(n - 1) + fibonacci(n - 2);
}

• Time Complexity: Exponential — O(2^n)

• Drawback: Recomputes the same values repeatedly.

Memoization (Top-Down DP)

Copyint fibonacci(int n, vector<int> &dp) {
    if (n <= 1) return n;
    if (dp[n] != -1) return dp[n];
    return dp[n] = fibonacci(n - 1, dp) + fibonacci(n - 2, dp);
}

// Usage:
int n = 10;
vector<int> dp(n + 1, -1);
int result = fibonacci(n, dp);

• Time Complexity: O(n)

• Space Complexity: O(n) for recursion stack and DP array

Tabulation (Bottom-Up DP)

Copyint fibonacci(int n) {
    if (n <= 1) return n;
    vector<int> dp(n + 1);
    dp[0] = 0;
    dp[1] = 1;

    for (int i = 2; i <= n; i++) {
        dp[i] = dp[i - 1] + dp[i - 2];
    }
    return dp[n];
}

• Time Complexity: O(n)

• Space Complexity: O(n)

Space Optimization

You don’t need to store the whole DP array, just the last two values.

Copyint fibonacci(int n) {
    if (n <= 1) return n;

    int prev2 = 0;  // f(0)
    int prev1 = 1;  // f(1)

    for (int i = 2; i <= n; i++) {
        int curr = prev1 + prev2;
        prev2 = prev1;
        prev1 = curr;
    }

    return prev1;
}

• Time Complexity: O(n)

• Space Complexity: O(1)