2Brute2Best
🔥0

DP — 1D Linear Pattern: Algorithmic Intuition, Sub-patterns & C++ Guide

The answer at position i is built from answers at a few earlier positions. Write that rule, then fill left to right.

3 sub-patterns · 8 questions

Remember this · DP — 1D Linear
Trigger
"Number of ways", "maximum/minimum up to i", choices at each step that depend on the previous one or two.
Think
If I knew the answer for every smaller prefix, how would I get the answer for i?
Key question
What does dp[i] mean in one sentence?
A

What is this pattern?

Dynamic Programming (DP) is recursion that remembers. You write the answer for position i using the answers for a few smaller positions, then fill those answers in order so each one is computed only once.

In 1D linear DP the state is one index:

  • dp[i] means one clear thing, e.g. "the number of ways to reach step i" or "the most money from the first i houses".
  • The rule (recurrence) builds dp[i] from dp[i − 1], dp[i − 2], … (or from every earlier dp[j]).
  • Base cases fill the first one or two cells by hand.
  • Order: fill left to right, so every cell you read is already done.

The usual path is always the same: plain recursion (correct but exponential) → memoization (store each answer the first time) → bottom-up table → keep only the cells the rule still reads (often two variables).

Counting the ways up a staircase with a notebook. Without the notebook you recount the ways to reach step 3 every time someone asks, again and again. With it, you write each step's count once — step 5's count is just step 4's plus step 3's, already on the page.

B

See it move

Ways to climb 5 stairs with 1- or 2-steps. First the plain recursion (orange = a subproblem solved before), then the same answers filled left to right, each once.

From recursion to a tablen = 5step 1/21
plain recursion
f(5)call
Solved so far
{ }
Work
calls
1
call f(5)

f(5) = f(4) + f(3): the last move was a 1-step or a 2-step.

House Robber. Purple = the two cells the rule reads, grey = cells the two-variable code has already dropped, green on nums = robbed, red = skipped.

Take or skip, one house at a timenums = [5, 1, 1, 5, 3]step 1/7
nums
0
1
2
3
4
5
1
1
5
3
dp
0
1
2
3
4
Kept
prev2
0
prev1
0
dp[i] = most money from houses 0..i

dp[i] = the most money from houses 0..i without robbing two neighbours. Before house 0 both kept values are 0.

C

How do I recognise it?

  • "Number of ways to reach / build / decode …" where each step has a few choices.

  • "Maximum / minimum total up to position i" and the choice at i depends on the previous one or two positions (take this one or skip it).

  • "Can the first i characters be split into valid pieces?" — try every last piece.

  • A brute-force recursion that calls itself on the same smaller input many times (draw the tree: the same f(3) appears in several branches).

  • The input is one array or string and the answer for a prefix helps the answer for a longer prefix.

Looks like DP — 1D Linear, but isn't

List every way to climb / split / decode
→ Backtracking

DP counts or optimises; it never lists. When the output itself is all the ways, you must generate them, and there can be exponentially many.

Maximum sum of a contiguous subarray
→ DP — Kadane

It is DP too, but the state is "best subarray ending at i", and you restart or extend. That is the Kadane pattern.

Pick some items (any order) to hit a total or capacity
→ DP — Knapsack

The state is the capacity / sum left, not the position in the array. Perfect Squares sits on the border: it is 1D over the number, but it is really an unbounded knapsack.

Always take the biggest / cheapest next option
→ Check greedy with a counterexample first

Greedy works only when a local choice can never hurt later (that's the Greedy pattern). House Robber, Min Cost Climbing Stairs and Perfect Squares all break greedy on small inputs.

D

How would I discover it from scratch?

Don't memorise “use dp — 1d linear”. Ask these questions in order — the pattern falls out.

Write the recursion that tries every choice: ways(n) = ways(n − 1) + ways(n − 2), or rob(i) = max(rob(i − 1), rob(i − 2) + nums[i]). It is correct, but every call branches, so it costs about O(2^N).

E

Sub-patterns

Same core idea, different rule for “valid”. Learn them in this order.

01

Fibonacci-style

3 questions

dp[i] is built from dp[i − 1] and dp[i − 2] only — the last step was a 1-step or a 2-step (or a 1-digit or 2-digit piece).

02

Take or skip

3 questions

At each element choose: take it (and you may not take its neighbour) or skip it. dp[i] = max(dp[i − 1], dp[i − 2] + value[i]).

03

Prefix segmentation

2 questions

dp[i] asks about the whole prefix of length i, and the rule tries every last piece s[j..i), reading dp[j] for many j.

F

Don't mix these up

Memoization (top-down) vs Tabulation (bottom-up)

Same states, same rule, same time. Memo keeps the recursion and fills cells only when asked; tabulation fills every cell in order with a loop, which is what lets you shrink the table to a few variables.

1D DP vs Greedy

If one small example shows the locally best choice losing (rob the biggest house, take the biggest square), you need DP. Greedy needs a proof that the local choice is always safe.

1D DP vs Backtracking

Both start from the same recursion. If the question asks for a count or a best value, the subproblems repeat → memoize (DP). If it asks you to list every answer, nothing repeats in the output → backtracking.

Climbing Stairs vs Decode Ways

Same shape (last piece is 1 or 2 long), but in Decode Ways a piece is allowed only if it's a valid code: '0' alone is not, and two digits must be 10–26.

G

Code templates (C++)

Fibonacci-style (two previous cells)

The base cases and the combine line are the only parts that change between problems (+ for counting ways, min(...) + cost for cheapest path, validity checks for Decode Ways).

fibonacci-template.cpp
// Fibonacci-style DP: dp[i] is built from dp[i - 1] and dp[i - 2] only,
// so two variables are enough. Shown for "ways to climb n stairs (1 or 2 steps)".
int climbWays(int n) {
    if (n <= 1) return 1;
    int prev2 = 1, prev1 = 1;          // dp[0], dp[1]
    for (int i = 2; i <= n; i++) {
        int cur = prev1 + prev2;       // last move was a 1-step or a 2-step
        prev2 = prev1;
        prev1 = cur;
    }
    return prev1;                      // dp[n]
}

Take or skip

skip keeps the previous best; take adds this element to the best that ends two back. For a circle (House Robber II), run it twice: without the first element, and without the last.

take-skip-template.cpp
// Take or skip: the best total from a[0..i] where no two taken elements are neighbours.
// dp[i] = max(skip = dp[i - 1], take = dp[i - 2] + a[i]).
long long takeSkip(const vector<int>& a, int from, int to) {   // inclusive range
    long long prev2 = 0, prev1 = 0;    // best up to i - 2, best up to i - 1
    for (int i = from; i <= to; i++) {
        long long cur = max(prev1, prev2 + a[i]);
        prev2 = prev1;
        prev1 = cur;
    }
    return prev1;
}
// Circle: first and last can't both be taken.
//   n == 1 ? a[0] : max(takeSkip(a, 0, n - 2), takeSkip(a, 1, n - 1))

Prefix segmentation

dp[i] = the first i characters can be split. Try every last piece s[j..i); limit j to the longest word to save time.

word-break-template.cpp
// Prefix segmentation: dp[i] = the first i characters can be split into words.
// Try every last piece s[j..i) and read dp[j].
bool canSplit(const string& s, const vector<string>& words) {
    unordered_set<string> dict(words.begin(), words.end());
    size_t longest = 0;
    for (auto& w : words) longest = max(longest, w.size());
    int n = s.size();
    vector<bool> dp(n + 1, false);
    dp[0] = true;                                  // the empty prefix splits trivially
    for (int i = 1; i <= n; i++)
        for (int j = i - 1; j >= 0 && i - j <= (int)longest; j--)
            if (dp[j] && dict.count(s.substr(j, i - j))) { dp[i] = true; break; }
    return dp[n];
}
Next
Start with Fibonacci-style