DP Quick Start¶

1. What problem does it solve?¶

2. The math¶

3. Lesson notes (10 August)¶

4. Worked solution — Composing Pyramids¶

5. How to recognise a DP¶

6. Common mistakes¶

7. Practice¶

2.1 The five blanks¶

2.2 Why \(2\min(\texttt{up}, \texttt{dn}) - 1\)¶

2.3 Trace on the sample¶

2.4 Cost¶

1. What is DP, really?¶

2. The 5-step recipe (use this every time)¶

3. Example A — Fibonacci (the "hello world" of DP)¶

4. Example B — Counting ways (Climbing Stairs)¶

5. Example C — Longest Increasing Subsequence (THE pattern for Q5)¶

6. Bridge to Q5 — Composing Pyramids¶

7. Cheat sheet¶

In one sentence

Dynamic programming fills a table of answers to smaller versions of the problem, in an order where every entry only needs entries that are already filled, so nothing is ever computed twice.

Example — AIO 2022 · Composing Pyramids (AIO 2022 Q5, lesson of 10 August)

A tune is a sequence of \(N\) notes \(P_1, \dots, P_N\). A pyramid is a sequence of the form \(x, x+1, \dots, x+k, \dots, x+1, x\): it climbs by exactly \(1\) to a top and comes back down by exactly \(1\) (a single note is also a pyramid). Delete as few notes as possible so that the notes that remain, in their original order, form a pyramid. Print the number of deleted notes.

Limits: \(N \le 10^5\), notes between \(1\) and \(10^5\).

Input          Output
6
2 1 3 4 2 1    3

Keeping 2 3 2 (positions 1, 3, 5) is a pyramid of length 3, so 3 notes are deleted.

The naive way. Try every subset of notes: \(2^N\) subsets. Impossible for \(N = 10^5\).

The DP way. "Deleting the fewest" is "keeping the longest". Split a pyramid at its top: the left half is a chain climbing by \(+1\) that ends at the top, the right half is a chain falling by \(-1\) that starts at the top. So we only need, for every position \(i\), the longest such chain ending at \(i\) and starting at \(i\). The lesson note below builds up to exactly that, through Fibonacci, climbing stairs and the longest increasing subsequence.

blank	Composing Pyramids (left half)
state	`up[i]` = longest chain \(\dots, P_i - 1, P_i\) of consecutive values that ends at position \(i\)
transition	`up[i] = f[P_i - 1] + 1`, where `f[v]` = best `up` among earlier positions holding value \(v\)
base	`f[v] = 0` for every \(v\) before we start, so a note with no predecessor gets `up[i] = 1`
order	\(i\) from left to right (so `f` only contains earlier positions)
answer	combine with the right half: \(\max_i \big(2\min(\texttt{up}[i], \texttt{dn}[i]) - 1\big)\)

dn[i] is the same thing from right to left: the longest chain \(P_i, P_i - 1, \dots\) starting at \(i\).

A pyramid with top at position \(i\) has the same number of notes on both sides of the top (it must return to the starting value \(x\)). The left side can be at most up[i] - 1 notes long, the right side at most dn[i] - 1, so both sides get \(\min(\texttt{up}[i], \texttt{dn}[i]) - 1\) notes, plus the top: \(2\min - 1\). The left chain uses only positions before \(i\) and the right chain only positions after \(i\), so no note is used twice.

\(P = (2, 1, 3, 4, 2, 1)\).

For example up[4] = 3 is the chain 2, 3, 4 (positions 1, 3, 4) and dn[3] = 3 is 3, 2, 1 (positions 3, 5, 6). The best pyramid has length \(3\), so \(6 - 3 = 3\) notes are deleted.

Two passes of \(O(1)\) work per note plus arrays of size \(10^5\) indexed by value: \(O(N + \max P)\).

Goal for today: understand DP well enough to solve Q5 (Composing Pyramids). Q5 is really just the "longest increasing subsequence" idea in disguise, so if you get the last example on this page, you get Q5.

Dynamic Programming = "solve a big problem by combining answers to smaller versions of the same problem, and never solve the same small version twice."

Two things must be true for DP to work:

Optimal substructure — the best answer to the big problem is built from the best answers to smaller sub-problems.
Overlapping subproblems — the same sub-problem shows up again and again, so it pays to store (memoize) each answer once.

If a problem has both, DP turns an exponential brute force into something polynomial.

Whenever you see a DP problem, fill in these 5 blanks:

Step	Question	Example (Fibonacci)
State	What does `dp[i]` mean?	`dp[i]` = the i-th Fibonacci number
Transition	How do I build `dp[i]` from smaller states?	`dp[i] = dp[i-1] + dp[i-2]`
Base case	Which states do I know for free?	`dp[0] = 0`, `dp[1] = 1`
Order	In what order do I fill the table?	`i` from small to large
Answer	Which state (or combo) is the final answer?	`dp[n]`

If you can write these 5 lines in words, the code writes itself.

Brute-force recursion recomputes fib(i) an exponential number of times. DP stores each value once, so it becomes O(n).

#include<bits/stdc++.h>

using namespace std;

using ll = long long;

void solve() {
    int n;
    cin >> n;

    // state: dp[i] = i-th Fibonacci number
    vector<ll> dp(n + 1);
    dp[0] = 0;                 // base case
    if (n >= 1) {
        dp[1] = 1;             // base case
    }
    for (int i = 2; i <= n; i++) {
        dp[i] = dp[i - 1] + dp[i - 2];   // transition
    }

    cout << dp[n] << "\n";     // answer
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int T = 1;
    for (int i = 0; i < T; i++) {
        solve();
    }
    return 0;
}

Takeaway: a DP is just a table you fill in a smart order.

You climb a staircase of n steps. Each move goes up 1 or 2 steps. How many distinct ways to reach the top?

State: dp[i] = number of ways to reach step i.
Transition: the last move was +1 (from i-1) or +2 (from i-2), so dp[i] = dp[i-1] + dp[i-2].
Base: dp[0] = 1 (one way to "already be there"), dp[1] = 1.
Answer: dp[n].

Notice this is the same recurrence as Fibonacci — many counting DPs reduce to "sum over the possible last moves." That phrase — "consider the last move" — is the single most useful trick for building a transition.

void solve() {
    int n;
    cin >> n;

    vector<ll> dp(n + 1, 0);
    dp[0] = 1;
    for (int i = 1; i <= n; i++) {
        dp[i] += dp[i - 1];            // last move was +1
        if (i >= 2) {
            dp[i] += dp[i - 2];        // last move was +2
        }
    }

    cout << dp[n] << "\n";
}

Given an array a of n numbers, find the length of the longest strictly increasing subsequence (you may delete elements, order stays the same).

Example: a = [3, 1, 4, 1, 5, 9, 2, 6] → answer 4 (e.g. 1, 4, 5, 6).

This introduces the pattern you must internalize for Q5:

dp[i] = the best answer for a subsequence that ENDS exactly at index i.

Why "ends at i"? Because then the transition is easy: to end at i, the previous element is some j < i with a[j] < a[i], and we extend that subsequence by one.

State: dp[i] = length of the longest increasing subsequence ending at i.
Transition: dp[i] = 1 + max(dp[j]) over all j < i with a[j] < a[i] (if no such j, then dp[i] = 1, the element alone).
Base: every dp[i] starts at 1.
Order: i left to right (so all j < i are ready).
Answer: max(dp[i]) over all i — the subsequence can end anywhere.

void solve() {
    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }

    // dp[i] = length of longest increasing subsequence ending at i
    vector<int> dp(n, 1);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < i; j++) {
            if (a[j] < a[i]) {
                dp[i] = max(dp[i], dp[j] + 1);
            }
        }
    }

    int ans = 0;
    for (int i = 0; i < n; i++) {
        ans = max(ans, dp[i]);
    }
    cout << ans << "\n";
}

This is O(n²). Good enough to understand the idea. Two habits to lock in:

"ending at i" makes transitions local and easy.
The final answer is a max over all ending positions, because we don't know in advance where the best subsequence stops.

Q5 asks for the longest pyramid subsequence: values go x, x+1, ..., top, ..., x+1, x (consecutive up, then consecutive down).

Split any pyramid at its top. Then it is just two chains glued together:

a chain of consecutive increasing values ending at the top, and
a chain of consecutive decreasing values starting at the top.

So we reuse the LIS idea twice, with one twist — the values must be consecutive (+1 each step), not merely increasing:

up[i] = longest chain of consecutive increasing values ending at i.
dn[i] = longest chain of consecutive decreasing values starting at i.

Compare with Example C: it's the exact same "ending at i" DP. The only change is the transition looks at the value a[i] - 1 instead of all smaller values — because "consecutive" means the previous value must be exactly one less.

The speed trick: instead of scanning all earlier j (the O(n²) inner loop), we keep a bucket indexed by value:

f[v] = best increasing chain seen so far that ends on value v.
Then up[i] = f[a[i] - 1] + 1, and we update f[a[i]].

Because the previous value in a consecutive chain is fixed (a[i]-1), one lookup replaces the whole inner loop → O(n + maxValue). That is the entire idea behind up, dn, f, g in the Q5 solution.

Once you have both, a pyramid with its top at i has length 2 * min(up[i], dn[i]) - 1 (both sides must be equally tall so the base lines up), and the answer to "how many to delete" is n - (longest pyramid).

See ../AIO2022/Composing Pyramids.cpp for the finished solution — now every line should read like the recipe above.

Always write the 5 lines first (state / transition / base / order / answer).
For "count the ways" or "best value" over a sequence: try dp[i] = something that ends at i, then transition by "what was the last step?"
The final answer is often max/sum over all dp[i], not just dp[n].
If a transition only ever needs one specific earlier value, replace the inner loop with a lookup table (that's the Q5 bucket trick).

This is the file from our 10 August lesson (the note above refers to it as ../AIO2022/Composing Pyramids.cpp). The sample files fib.cpp, stairs.cpp and lis.cpp it mentions are the three examples already shown in §3.

#include<bits/stdc++.h>

using namespace std;

using ll = long long;

const int MAXV = 100001;

void solve() {
    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }

    // up[i]: longest chain of consecutive increasing values ending at i
    // dn[i]: longest chain of consecutive decreasing values starting at i
    vector<int> up(n), dn(n);

    // f[v]: longest chain of consecutive increasing values ending with value v
    vector<int> f(MAXV + 2, 0), g(MAXV + 2, 0);


    for (int i = 0; i < n; i++) {
        up[i] = f[a[i] - 1] + 1;
        f[a[i]] = max(f[a[i]], up[i]);
    }

    for (int i = n - 1; i >= 0; i--) {
        dn[i] = g[a[i] - 1] + 1;
        g[a[i]] = max(g[a[i]], dn[i]);
    }

    int best = 1;
    for (int i = 0; i < n; i++) {
        best = max(best, 2 * min(up[i], dn[i]) - 1);
    }

    cout << n - best << "\n";
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int T = 1;
    for (int i = 0; i < T; i++) {
        solve();
    }
    return 0;
}

Sign	Typical state
"number of ways to …"	`dp[i]` = ways to reach step \(i\); sum over the last move
"longest / best subsequence"	`dp[i]` = best answer ending at \(i\)
brute force tries the same smaller question many times	store that question's answer in a table
the next choice only depends on a small summary of the past	that summary is the state

State not written down

If you cannot finish the sentence "dp[i] means …" precisely, the transition will be wrong. Write the five blanks first.

Wrong filling order

Every value the transition reads must already be final. In Composing Pyramids, f must only contain positions to the left when computing up[i], which is why the loops go left-to-right for up and right-to-left for dn.

Answer is not dp[n]

For "ending at \(i\)" states the best chain can end anywhere: take the maximum over all \(i\).

Index a[i] - 1 out of range

Values start at \(1\), so a[i] - 1 can be \(0\). Make the value arrays large enough and leave index \(0\) as the empty base case.

\(2\min - 1\)

Problem	Where	Idea
AIO 2022 · Composing Pyramids	AIO 2022 Q5	this page
AtCoder EDU DP · A Frog 1	AtCoder	`dp[i]` from `dp[i-1]` and `dp[i-2]`
CSES · Dice Combinations	CSES	count ways, sum over the last die
AtCoder EDU DP · D Knapsack 1	AtCoder	next step after this page

Credits & licenses

§3 is our Dynamic Programming — Quick Start handout of 10 August, unchanged apart from heading levels (its short list of sample file names is left out; see §4). §4 is the lesson's solution file, unchanged.
Example summary, five-blank table for the problem, the \(2\min-1\) argument, trace, mistakes and practice list are ours.