What is Dynamic Programming?

Dynamic Programming is an optimization technique used when a problem has overlapping subproblems and optimal substructure.

Instead of solving the same subproblem repeatedly, we:

1. Solve it once.
2. Store (memoize) the answer.
3. Reuse it whenever needed.

Two Ways to Write DP

1. Top-Down (Memoization)

Start from the original problem.

Use recursion.

Store answers.

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

int fib(int n) {

    if (n <= 1)
        return n;

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

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

2. Bottom-Up (Tabulation)

Start from the smallest problem.

Build upwards.

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];

Space Optimization (Tabulation)

Notice

dp[i] depends only on

dp[i-1]

dp[i-2]

So the whole array isn't needed.

int prev2 = 0;
int prev1 = 1;

for (int i = 2; i <= n; i++) {

    int curr = prev1 + prev2;

    prev2 = prev1;
    prev1 = curr;
}

return prev1;

Common DP Categories

Memory Trick

Make a Decision Tree if the problem is like that see if other decision trees can be eliminated with only one tree remaining

Whenever you see a recursive solution, ask yourself:

"Am I solving the same subproblem more than once?"

• No → Plain recursion or another algorithm may be sufficient.
• Yes → Consider Dynamic Programming.

Then ask:

"What is the smallest piece of information that uniquely defines this subproblem?"

That becomes your DP state.

Once you have the state, the rest follows:

1. Define the state.
2. Write the transition (recurrence).
3. Set the base cases.
4. Implement with memoization or tabulation.
5. Optimize space if only a few previous states are needed.