DP Bottom-Up (Tabulation)

Concept

Bottom-up DP builds the solution iteratively from the smallest subproblems up to the original problem. Fill a table starting from base cases and use previously computed values to derive the next ones. No recursion needed — just loops.

When to Use

• ▸Same problems as top-down DP but when you want to avoid recursion overhead
• ▸When all subproblems need to be computed anyway
• ▸When you want to optimize space (e.g., only keeping the last 2 rows)
• ▸Fibonacci, path counting, knapsack, coin change, etc.

Intuition

Instead of starting from the big problem and breaking it down, start from the smallest pieces and build up. Like building a wall brick by brick — each brick rests on the ones below it. For Fibonacci, compute F(0), F(1), F(2), ... in order. By the time you need F(n), all smaller values are already in the table.

Complexity

Template Code

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

int main(){
    ios_base::sync_with_stdio(0), cin.tie(0);
    int n;
    cin >> n;

    vector<int> dp(n+1);
    dp[0] = 1;
    dp[1] = 1;

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

    cout << dp[n];

    return 0;
}

// Sample Input:
// 10
//
// Sample Output:
// 89