DP Top-Down (Memoization)

Concept

Top-down DP solves problems recursively but stores results of subproblems in a table (memoization) to avoid recomputation. Start from the original problem, break it into subproblems, and cache each result. If a subproblem was already solved, return the cached answer instantly.

When to Use

  • ▸Problems with overlapping subproblems and optimal substructure
  • ▸When the recursive solution is intuitive but too slow (exponential)
  • ▸Fibonacci, path counting, knapsack, edit distance, coin change, etc.
  • ▸When not all subproblems need to be solved (sparse state space)

Intuition

Think of it as 'lazy evaluation'. You only solve subproblems when you actually need them, and you write down the answer so you never solve the same thing twice. It's like a student who solves homework problems and keeps a notebook — if the same problem appears on an exam, they just look it up instead of re-solving it.

Complexity

Time
O(n) for Fibonacci (each state computed once)
Space
O(n)

Template Code

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

long long fiboDp(int n, vector<int> &dp){
    if(n==0 || n==1) return 1;

    if(dp[n] != -1) return dp[n];

    return dp[n] = fiboDp(n-1, dp) + fiboDp(n-2, dp);
}

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

    vector<int> dp(n+1, -1);
    cout << fiboDp(n, dp);

    return 0;
}

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