Dynamic Programming

From representation to repeated decisions

In Introduction to Data Structures and Algorithms, we focused on representation, access patterns, complexity, and recognizing patterns instead of memorizing recipes.

Dynamic Programming is where those ideas become especially valuable: the hardest part is rarely writing the loop. It is deciding what a subproblem means.

Interview DP is about turning a messy decision process into:

• a small set of states
• a precise transition
• reliable base cases
• an execution order that computes every state once

This lesson focuses on the mental model you need for FAANG-style DP questions, especially the ones that look like small twists on classics.

The two-part DP test

A problem is a good DP candidate when both are true:

1. Optimal substructure: the best answer for a larger problem can be built from best answers to smaller problems.
2. Overlapping subproblems: the same smaller problem appears again and again.

A useful interview question is:

If I draw the brute-force recursion tree, do identical calls show up in different branches?

If yes, DP may turn exponential exploration into polynomial computation.

Common DP signals

• choose / skip
• partition here or keep going
• match / do not match
• take one step or two steps
• use this coin/item or move past it
• best score up to index i
• number of ways to reach amount x

Do not force DP just because the prompt asks for a maximum or minimum. Greedy, sorting, two pointers, or graph traversal may be cleaner depending on the access pattern.

You are exploring a brute-force recursive solution. Different decision paths repeatedly call the same function with the same parameters.

What is the strongest signal that Dynamic Programming may help?

Define the state before the code

A DP state is a contract: it says exactly what a stored value means.

For example, in a house-robber-style problem:

dp[i] = maximum money we can rob from houses 0..i

That contract immediately suggests the transition:

• skip house i: answer is dp[i - 1]
• rob house i: answer is dp[i - 2] + nums[i]

So:

dp[i] = max(dp[i - 1], dp[i - 2] + nums[i])

A strong state definition includes

• scope: prefix, suffix, interval, remaining amount, capacity, index pair
• value meaning: max score, min cost, number of ways, boolean possible
• decision boundary: what choice is being made at this state

If you cannot say what dp[i][j] means in one sentence, pause. The bug is probably in the definition, not the syntax.

Memoization: preserve the recursive story

Top-down DP is often the fastest way to reach a correct interview solution.

You write the natural recursive function, then cache each state the first time it is computed.

Example state:

solve(i) = minimum cost to reach step i

From step i, the last jump came from either i - 1 or i - 2.

This keeps the reasoning close to the brute-force recurrence while avoiding repeated work.

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

int minCostClimbingStairs(vector<int>& cost) {
    int n = cost.size();
    vector<int> memo(n + 1, -1);

    function<int(int)> solve = [&](int i) -> int {
        if (i <= 1) return 0; // You may start at step 0 or 1.

        int& ans = memo[i];
        if (ans != -1) return ans;

        int fromPrev = solve(i - 1) + cost[i - 1];
        int fromTwoBack = solve(i - 2) + cost[i - 2];
        ans = min(fromPrev, fromTwoBack);
        return ans;
    };

    return solve(n);
}

int main() {
    vector<int> cost = {10, 15, 20};
    cout << "Minimum cost: " << minCostClimbingStairs(cost) << '\n';
    return 0;
}
```

True or false:

Every recursive solution with a base case should be converted into Dynamic Programming.

Tabulation: choose the computation order

Bottom-up DP removes recursion and fills smaller states before larger states.

For coin-change combinations:

dp[sum] = number of ways to make sum using coins processed so far

The order matters:

• loop over coins outside
• loop sum increasing inside

That counts combinations like 2 + 3 and 3 + 2 as the same kind of construction when coins are processed in fixed order.

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

long long countWays(vector<int> coins, int amount) {
    vector<long long> dp(amount + 1, 0);
    dp[0] = 1; // One way to make zero: choose nothing.

    for (int coin : coins) {
        for (int sum = coin; sum <= amount; ++sum) {
            dp[sum] += dp[sum - coin];
        }
    }

    return dp[amount];
}

int main() {
    vector<int> coins = {1, 2, 5};
    int amount = 5;
    cout << "Ways to make " << amount << ": " << countWays(coins, amount) << '\n';
    return 0;
}
```

In the bottom-up coin-change combinations DP, we use:

dp[sum] += _____;

Fill in the missing expression.

Space optimization is about dependencies

You can compress DP when the transition only needs a limited slice of previous information.

Examples:

• Fibonacci-like transitions need only the previous two values.
• Prefix DP often needs only the previous row or previous column.
• 1D capacity DP may need careful loop direction to avoid reusing an item too many times.

The dependency question

Before compressing, ask:

When computing this state, which older states must still be unchanged?

That question prevents a common interview bug: overwriting a value before all states that depend on it have read it.

Sometimes the value is not enough

Interviewers may ask not only for the best value, but also for the actual sequence or choices.

The pattern is simple:

• compute the DP value
• store a parent pointer or previous choice
• walk backward from the best final state
• reverse the result if needed

Here is Longest Increasing Subsequence with reconstruction. We will stay within array DP here; later lessons will handle graph and tree-specific structures separately.

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

int main() {
    vector<int> a = {10, 9, 2, 5, 3, 7, 101, 18};
    int n = a.size();

    vector<int> dp(n, 1), parent(n, -1);
    int best = 0;

    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < i; ++j) {
            if (a[j] < a[i] && dp[j] + 1 > dp[i]) {
                dp[i] = dp[j] + 1;
                parent[i] = j;
            }
        }
        if (dp[i] > dp[best]) best = i;
    }

    vector<int> lis;
    for (int cur = best; cur != -1; cur = parent[cur]) {
        lis.push_back(a[cur]);
    }
    reverse(lis.begin(), lis.end());

    cout << "LIS length: " << lis.size() << '\n';
    cout << "One LIS: ";
    for (int x : lis) cout << x << ' ';
    cout << '\n';

    return 0;
}
```

In a 1D 0/1 knapsack-style DP, each item may be used at most once.

When processing one item, which capacity direction prevents reusing that same item during the same iteration?

Your DP interview flow

Use this compact checklist when a problem smells like DP:

1. Brute-force decisions: What choices exist at each step?
2. State contract: What does each dp[...] value mean?
3. Transition: How do choices combine smaller answers?
4. Base cases: What states are known without computation?
5. Order: Top-down memo or bottom-up table?
6. Answer location: Is the answer at dp[n], max over states, or a reconstructed path?
7. Complexity: Number of states times work per state.

Dynamic Programming rewards precision. If the state is clean, the code usually follows.

Next, we will move from repeated subproblems to connectivity and traversal patterns in Graph Algorithms.