Dynamic Programming -- 1D Introduction

Solve problems by breaking them into overlapping subproblems, storing results to avoid recomputation. The foundation of half of all CF problems rated 1200+.

Difficulty: [Beginner] Prerequisites: Arrays and StringsCF Rating Range: 1000-1400

Quick Revisit
USE WHEN: sequence where each element depends on a fixed window of previous elements
INVARIANT: dp[i] = optimal answer considering the first i elements
TIME: O(n) to O(n*k) | SPACE: O(n), often O(1) with rolling variables
CLASSIC BUG: wrong base case -- dp[0] = 1 for counting paths vs dp[0] = 0 for min-cost
PRACTICE: DP Practice Ladder

Intuition
C++ STL Reference
Implementation
Operations Reference
Problem Patterns & Tricks
Contest Cheat Sheet
Gotchas & Debugging
Self-Test
Practice Problems
Further Reading
Code Reading Exercise

Contest Frequency: *** Common -- appears in most contests

Intuition

You need to climb a staircase of 6 steps, taking 1 or 2 steps at a time, and you want the total number of ways. You write a recursive function -- and it takes forever. Here's why. Compute $F (6)$ with naive recursion. Every call spawns two more:

                          F(6)
                        /      \
                    F(5)        F(4)
                   /    \       /    \
               F(4)    F(3)  F(3)   F(2)
              /   \    / \    / \
          F(3) F(2) F(2) F(1) F(2) F(1)
         /  \
      F(2) F(1)

Count the damage:

  Subproblem    Times computed (naive)    Times needed
  ----------    ----------------------    ------------
  F(6)                 1                       1
  F(5)                 1                       1
  F(4)                 2                       1
  F(3)                 3                       1
  F(2)                 5                       1
  F(1)                 3                       1
  F(0)                 2                       1
                      ---                     ---
  Total calls:        17*                      7

  * Full binary tree has 25 nodes for deeper unrolling.
    In general: O(2^n) calls vs O(n) unique subproblems.

$F (3)$ is computed 3 times. $F (2)$ is computed 5 times. We are paying exponential cost for a problem with only 7 distinct subproblems.

If the same subproblem appears multiple times, solve it once, store the answer, and reuse it -- this is dynamic programming.

Think of it as writing answers on sticky notes. The first time you compute $F (3) = 2$ , you write "F(3) = 2" on a note and stick it to the wall. Next time someone asks for $F (3)$ , you glance at the wall instead of recalculating. One lookup replaces an entire subtree of redundant work.

Another way to see DP: it's finding the shortest (or longest) path on a DAG where each state is a node and each transition is a directed edge. The staircase problem is really a DAG with nodes $0, 1, \dots, 6$ and edges from $i$ to $i + 1$ and $i + 2$ . Computing dp[i] is computing the number of paths from node 0 to node $i$ . This graph perspective makes it obvious why DP works -- a DAG has a topological order, so you can process nodes left to right and never revisit one.

Visual Walkthrough

Fill dp[0..6] left to right. Each cell depends only on two earlier cells that are already filled -- no recursion needed.

  Step 0 (base cases):
    dp[0] = 0    dp[1] = 1
    [  0  ][  1  ][     ][     ][     ][     ][     ]

  Step 1:  dp[2] = dp[1] + dp[0] = 1 + 0 = 1
    [  0  ][  1  ][  1  ][     ][     ][     ][     ]

  Step 2:  dp[3] = dp[2] + dp[1] = 1 + 1 = 2
    [  0  ][  1  ][  1  ][  2  ][     ][     ][     ]

  Step 3:  dp[4] = dp[3] + dp[2] = 2 + 1 = 3
    [  0  ][  1  ][  1  ][  2  ][  3  ][     ][     ]

  Step 4:  dp[5] = dp[4] + dp[3] = 3 + 2 = 5
    [  0  ][  1  ][  1  ][  2  ][  3  ][  5  ][     ]

  Step 5:  dp[6] = dp[5] + dp[4] = 5 + 3 = 8
    [  0  ][  1  ][  1  ][  2  ][  3  ][  5  ][  8  ]

  Total operations: 5 additions.  Compare with 25 recursive calls.

Dependencies flow strictly left-to-right:

    dp[0]  dp[1]  dp[2]  dp[3]  dp[4]  dp[5]  dp[6]
    +------+------+------+------+------+------+------+
    |  0   |  1   |  1   |  2   |  3   |  5   |  8   |
    +------+------+------+------+------+------+------+
                     ^      ^      ^      ^      ^
                     |      |      |      |      |
                  dp[0]  dp[1]  dp[2]  dp[3]  dp[4]
                + dp[1] + dp[2] + dp[3] + dp[4] + dp[5]

The Invariant

Invariant: dp[i] = the answer to subproblem $i$ . Once filled, its value never changes. Each subproblem is solved exactly once.

This is what makes DP correct: we process subproblems in an order that guarantees every dependency is already resolved before we need it.

State identification checklist -- "How to identify the right DP state":

What decision am I making at each step? (e.g., which coin to use, whether to include element $i$ )
What information do I need to make that decision? -- that is your state. Strip away anything the optimal answer does not depend on.
Does the state have optimal substructure? Can the optimal solution to the whole be built from optimal solutions to sub-states?
Are there overlapping subproblems? Do different decision paths lead to the same sub-state? If yes, DP pays off.

Top-down vs bottom-up trade-offs:

Aspect	Top-down (memoization)	Bottom-up (tabulation)
Style	Recursive + cache (`map` or `vector`)	Iterative loop filling a table
Ease of writing	Natural -- translates the recurrence directly	Must determine correct fill order
States computed	Only those reachable from the root call	All states in the table, even unused ones
Overhead	Recursion stack + hash/lookup overhead	No recursion; cache-friendly sequential access
Stack limit	Risk of stack overflow for $n > 10^{5}$	No stack issues
Best when	State space is sparse or hard to enumerate	State space is dense and fill order is obvious

Rule of thumb: Use top-down when the state space is sparse or the recurrence is complex. Use bottom-up (the contest default) when the state space is dense and the fill order is clear.

DP vs greedy decision framework:

  Does a greedy-choice property hold?
       |
       +-- YES (provable via exchange argument) --> use GREEDY
       |
       +-- NO / unsure
              |
              Does the problem have optimal substructure
              AND overlapping subproblems?
                   |
                   +-- YES --> use DP
                   |
                   +-- No overlapping subproblems --> DIVIDE & CONQUER

When in doubt, try greedy first. Attempt an exchange argument: "If the greedy choice is not in the optimal solution, can I swap it in without making things worse?" If the argument fails (e.g., coin change with arbitrary denominations: greedy picks the largest coin, but ${1, 3, 4}$ target $6$ gives $4 + 1 + 1 = 3$ coins while $3 + 3 = 2$ coins), fall back to DP.

Coin change dependency graph -- for coins ${1, 3, 4}$ , target $6$ :

  Each dp[i] = min coins to make amount i.
  Arrows show which earlier states dp[6] depends on:

       ┌──── coin 4 ────┐
       │   ┌── coin 3 ──┤
       │   │   ┌ coin 1 ┤
       ▼   ▼   ▼        │
  dp: [0] [1] [2] [1] [1] [2] [ ? ]
       0   1   2   3   4   5    6

  dp[6] = min(dp[6-1]+1, dp[6-3]+1, dp[6-4]+1)
         = min(dp[5]+1,   dp[3]+1,   dp[2]+1)
         = min(  3,         2,         3     )
         = 2  <- comes from dp[3], meaning coins 3+3

What the Code Won't Teach You

State semantics determine everything. Two people can write dp[i] and mean completely different things. "LIS ending exactly at index i" gives a harder but more useful recurrence than "best LIS considering the first i elements." The first enables the patience sorting optimization; the second doesn't. Choosing the right state definition requires judgment built from experience -- no template will tell you which meaning of dp[i] leads to the cleanest transition.

When 1D DP becomes the wrong tool. If the transition requires information that a single index can't capture, you need more dimensions. The test: "If I had two inputs reaching the same state i but differing in some property X, would my transition give different answers?" If yes, X must become part of the state, and your 1D DP becomes 2D.

The LIS trick is not magic. The $O (n \log n)$ patience sorting trick feels like a completely different algorithm, but it's the same DP with a reformulated state. Instead of asking "what's the LIS ending at position i?", ask "what's the smallest ending element of any increasing subsequence of length k?" That reformulation preserves correctness while enabling binary search. The pattern -- reformulate what you store to enable a faster data structure -- recurs throughout competitive programming (convex hull trick, slope trick, etc.).

The real bottleneck is writing the transition, not the framework. Beginners spend time worrying about top-down vs. bottom-up, or whether to use memoization. None of that matters. The hard part is always the same: given dp[i], write the exact recurrence that computes it from earlier states. Once you have the recurrence on paper and you're confident it's correct, the code writes itself in under 5 minutes. If you're staring at the screen unsure what to type, the problem isn't coding -- it's that your recurrence is wrong or incomplete. Step away from the keyboard and think on paper.

Greedy and DP feel similar until they don't. Many 1D DP problems look like they could be greedy: "just always pick the best option." The coin change problem demonstrates exactly why greedy fails -- choosing the largest coin first (greedy) gives 4+4+4 = 3 coins for amount 12 with coins {1, 3, 4}, but DP finds 4+4+4 = 3 while greedy might fail for other denominations like {1, 3, 5} with amount 9: greedy gives 5+3+1 = 3 coins, but DP also gives 3+3+3 = 3. The real danger cases are subtler. If you can't prove the greedy choice property (that a locally optimal choice is globally safe), you need DP. The inability to prove greedy correctness is itself the signal to switch to DP.

Printing the actual solution, not just the optimal value. Almost every contest DP problem eventually asks you to reconstruct the solution -- not just "what's the minimum cost?" but "which coins did you use?" The technique is always the same: store a parent or choice array alongside dp, then trace back from the final state. But the tricky part is that multiple paths can yield the same optimal value. If the problem asks for the lexicographically smallest solution, you need to be deliberate about which predecessor you record -- and that tie-breaking logic is where bugs hide.

When to Reach for This

Trigger phrases in problem statements:

"minimum cost to ..."
"maximum profit / score"
"count the number of ways"
"optimal substructure + overlapping subproblems"
"how many distinct paths"

Counter-examples -- when DP is NOT the answer:

No overlapping subproblems: merge sort, binary search -- use divide-and-conquer instead.
Greedy-choice property holds: activity selection, fractional knapsack -- use greedy instead.
State space too large: if the DP table would exceed memory or time, look for mathematical shortcuts or greedy arguments.

C++ STL Reference

Function / Class	Header	What it does	Time
`vector<int> dp(n, val)`	`<vector>`	Create DP array of size `n` initialized to `val`	$O (n)$
`fill(begin, end, val)`	`<algorithm>`	Reset DP array between test cases	$O (n)$
`min(a, b)` / `max(a, b)`	`<algorithm>`	Used in virtually every DP recurrence	$O (1)$
`*min_element(begin, end)`	`<algorithm>`	Find global min in DP array (e.g., min-cost)	$O (n)$
`*max_element(begin, end)`	`<algorithm>`	Find answer in LIS-style DPs where answer = max over all `dp[i]`	$O (n)$
`lower_bound(begin, end, val)`	`<algorithm>`	Binary search in patience-sorting LIS ( $O (n \log n)$ )	$O (\log n)$
`accumulate(begin, end, 0LL)`	`<numeric>`	Sum DP array (counting problems)	$O (n)$
`INT_MAX` / `LLONG_MAX`	`<climits>`	Infinity sentinel for min-type DPs	--
`array<int, N>`	`<array>`	Fixed-size DP array when $N$ is compile-time constant	$O (1)$ create

Implementation (Contest-Ready)

Version 1: Coin Change -- Minimum Coins (Minimal)

cpp

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

int main() {
    int n, target;
    cin >> n >> target;
    vector<int> coins(n);
    for (auto& c : coins) cin >> c;

    const int INF = 1e9;
    vector<int> dp(target + 1, INF);
    dp[0] = 0;
    for (int i = 1; i <= target; ++i)
        for (int c : coins)
            if (c <= i && dp[i - c] < INF)
                dp[i] = min(dp[i], dp[i - c] + 1);

    cout << (dp[target] >= INF ? -1 : dp[target]) << "\n";
}

Version 1: Coin Change -- Explained

cpp

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

int main() {
    int n, target;
    cin >> n >> target;
    vector<int> coins(n);
    for (auto& c : coins) cin >> c;

    // dp[i] = min coins to make amount i, INF means impossible
    const int INF = 1e9;
    vector<int> dp(target + 1, INF);
    dp[0] = 0;  // base case: 0 coins to make amount 0

    for (int i = 1; i <= target; ++i)
        for (int c : coins)
            // Only consider coin c if it fits and the remainder is reachable
            if (c <= i && dp[i - c] < INF)
                dp[i] = min(dp[i], dp[i - c] + 1);

    // dp[target] == INF means no combination works
    cout << (dp[target] >= INF ? -1 : dp[target]) << "\n";
}

Version 2: Longest Increasing Subsequence -- $O (n^{2})$ (Minimal)

cpp

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

int main() {
    int n;
    cin >> n;
    vector<int> a(n);
    for (auto& x : a) cin >> x;

    vector<int> dp(n, 1);
    for (int i = 1; i < n; ++i)
        for (int j = 0; j < i; ++j)
            if (a[j] < a[i])
                dp[i] = max(dp[i], dp[j] + 1);

    cout << *max_element(dp.begin(), dp.end()) << "\n";
}

Version 2: LIS -- Explained

cpp

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

int main() {
    int n;
    cin >> n;
    vector<int> a(n);
    for (auto& x : a) cin >> x;

    // dp[i] = length of longest increasing subsequence ending at index i
    vector<int> dp(n, 1);  // every element alone is a subsequence of length 1

    for (int i = 1; i < n; ++i)
        for (int j = 0; j < i; ++j)
            // Can we extend the LIS ending at j by appending a[i]?
            if (a[j] < a[i])
                dp[i] = max(dp[i], dp[j] + 1);

    // Answer is the max over all ending positions
    cout << *max_element(dp.begin(), dp.end()) << "\n";
}

Bonus: LIS in $O (n \log n)$ -- Patience Sorting

cpp

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

int main() {
    int n;
    cin >> n;
    vector<int> a(n);
    for (auto& x : a) cin >> x;

    // tails[i] = smallest tail element of any increasing subsequence of length i+1
    vector<int> tails;
    for (int x : a) {
        auto it = lower_bound(tails.begin(), tails.end(), x);
        if (it == tails.end()) tails.push_back(x);
        else *it = x;
    }
    cout << tails.size() << "\n";
}

Operations Reference

Use this table to pick the right recurrence and estimate runtime before you start coding.

Problem	Recurrence	Time	Space	Notes
Fibonacci / staircase counting	$d p [i] = d p [i - 1] + d p [i - 2]$	$O (n)$	$O (n)$ , $O (1)$ with rolling	Space-optimize to 2 variables
Coin change (min coins)	$d p [i] = min_{c} (d p [i - c]) + 1$	$O (n \cdot k)$	$O (n)$	$k$ = number of coin types
Coin change (count ways)	$d p [i] = \sum_{c} d p [i - c]$	$O (n \cdot k)$	$O (n)$	Order matters vs not matters changes loop nesting
LIS ( $O (n^{2})$ )	$d p [i] = max_{j < i} (d p [j] + 1)$	$O (n^{2})$	$O (n)$	Simple, sufficient for $n \leq 5000$
LIS ( $O (n \log n)$ )	Patience sorting	$O (n \log n)$	$O (n)$	Use for $n \leq 10^{5}$
Max subarray sum (Kadane)	$d p [i] = max (a [i], d p [i - 1] + a [i])$	$O (n)$	$O (1)$	Technically DP, often classified as greedy

Problem Patterns & Tricks

Pattern 1: Staircase / Path Counting

"How many ways to reach step $n$ if you can take 1 or 2 steps?" Direct Fibonacci variant. Generalize: if steps are from a set $S$ , it becomes a coin-change counting problem.

cpp

dp[0] = 1;  // one way to stand at start
for (int i = 1; i <= n; ++i) {
    if (i >= 1) dp[i] += dp[i - 1];
    if (i >= 2) dp[i] += dp[i - 2];
}

CF examples: CF 1195C -- Basketball Exercise, CF 545C -- Woodcutters

Pattern 2: Minimum / Maximum Cost

"Find the minimum cost to reach state $n$ ." Each state tries all possible "last moves" and picks the best. Coin change, minimum path cost, and many scheduling problems.

cpp

dp[0] = 0;
for (int i = 1; i <= n; ++i)
    for (auto [cost, step] : transitions)
        if (i >= step)
            dp[i] = min(dp[i], dp[i - step] + cost);

CF examples: CF 1324D -- Pair of Topics, CF 189A -- Cut Ribbon

Pattern 3: Longest Increasing Subsequence (LIS)

Two variants: $O (n^{2})$ for small $n$ (look back at all previous), $O (n \log n)$ patience sorting for large $n$ . Many problems reduce to LIS after reformulation.

Variant -- Longest Non-Decreasing Subsequence: Replace lower_bound with upper_bound in patience sorting.

CF examples: CF 340D -- Bubble Sort Graph, CF 1385E -- Directing Edges

Pattern 4: Coin Change / Knapsack Variants

Count combinations (order doesn't matter): Loop coins in outer loop, amounts in inner loop. Count permutations (order matters): Loop amounts in outer loop, coins in inner loop.

cpp

// Combinations (outer=coins): each coin considered once per "layer"
for (int c : coins)
    for (int i = c; i <= target; ++i)
        dp[i] += dp[i - c];

// Permutations (outer=amounts): all coins at each amount
for (int i = 1; i <= target; ++i)
    for (int c : coins)
        if (i >= c) dp[i] += dp[i - c];

Why the loop order matters -- fill direction side by side:

  COMBINATIONS (coins outer)          PERMUTATIONS (amounts outer)
  ─────────────────────────────       ─────────────────────────────
  for each coin c:                    for each amount i:
    for i = c to target:               for each coin c:
      dp[i] += dp[i-c]                   dp[i] += dp[i-c]

  Coins={1,3}, target=4               Coins={1,3}, target=4

  Pass c=1:                           i=1: try c=1 -> dp[1]+=dp[0]
    dp[1]+=dp[0], dp[2]+=dp[1],      i=2: try c=1 -> dp[2]+=dp[1]
    dp[3]+=dp[2], dp[4]+=dp[3]       i=3: try c=1 -> dp[3]+=dp[2]
  Pass c=3:                                 try c=3 -> dp[3]+=dp[0]
    dp[3]+=dp[0], dp[4]+=dp[1]       i=4: try c=1 -> dp[4]+=dp[3]
                                            try c=3 -> dp[4]+=dp[1]
  dp: [1, 1, 1, 2, 2]                dp: [1, 1, 1, 2, 3]

  Combinations: {1,3} and {3,1}      Permutations: {1,3} and {3,1}
  count as ONE way.                   count as TWO ways.

CF examples: CF 1516C -- Baby Ehab Partitions Again, CF 755C -- PolandBall and Forest

Pattern 5: State Reduction / Space Optimization

When dp[i] depends only on dp[i-1] (or a fixed window of previous states), you don't need the full array. Roll two variables or a small circular buffer.

cpp

// Fibonacci with O(1) space
int a = 0, b = 1;
for (int i = 2; i <= n; ++i) {
    int c = a + b;
    a = b;
    b = c;
}
// answer is b

CF examples: CF 1476A -- K-divisible Sum, CF 580A -- Kefa and First Steps

Pattern 6: Kadane's Algorithm (Max Subarray)

$d p [i] = max (a [i], d p [i - 1] + a [i])$ . Either start a new subarray at $i$ or extend the previous one. Track the running max.

cpp

long long cur = 0, best = LLONG_MIN;
for (int i = 0; i < n; ++i) {
    cur = max((long long)a[i], cur + a[i]);
    best = max(best, cur);
}

CF examples: CF 1796B -- Asterisk-Minor Template, CF 1155D -- Beautiful Array

Contest Cheat Sheet

+---------------------------------------------------------------+
|              DYNAMIC PROGRAMMING -- 1D (AL-26)                |
+---------------------------------------------------------------+
| WHEN TO USE:                                                  |
|  - "Min/max/count" + small state space (n <= 1e6 for O(n))   |
|  - Greedy fails (e.g. arbitrary coin denominations)           |
|  - Problem has optimal substructure + overlapping subproblems |
+---------------------------------------------------------------+
| TEMPLATE (min-cost):                                          |
|   vector<int> dp(n+1, INF);                                  |
|   dp[0] = 0;                                                 |
|   for (int i = 1; i <= n; ++i)                               |
|       for (auto& t : transitions)                             |
|           dp[i] = min(dp[i], dp[i-t.step] + t.cost);         |
+---------------------------------------------------------------+
| TEMPLATE (count ways):                                        |
|   vector<long long> dp(n+1, 0);                              |
|   dp[0] = 1;                                                 |
|   for (int i = 1; i <= n; ++i)                               |
|       for (auto& s : steps)                                   |
|           if (i >= s) dp[i] = (dp[i] + dp[i-s]) % MOD;      |
+---------------------------------------------------------------+
| LIS (O(n log n)):                                             |
|   vector<int> tails;                                          |
|   for (int x : a) {                                           |
|       auto it = lower_bound(tails.begin(),tails.end(),x);    |
|       if (it == tails.end()) tails.push_back(x);             |
|       else *it = x;                                           |
|   }  // answer = tails.size()                                 |
+---------------------------------------------------------------+
| BASE CASES:  dp[0]=0 (min) | dp[0]=1 (count) | dp[i]=1 (LIS)|
| COMPLEXITY:  O(n*k) typical | O(n log n) LIS                 |
| WATCH OUT:   base cases | off-by-one | overflow | INF choice  |
+---------------------------------------------------------------+

Gotchas & Debugging

Wrong base case. For counting problems, dp[0] = 1 (there is one way to do nothing). For min-cost, dp[0] = 0 (zero cost for nothing). Getting this wrong silently gives wrong answers on all test cases.
Off-by-one in array bounds. If dp has size target + 1, valid indices are 0..target. Writing dp[target + 1] is undefined behavior. When the target is large, double-check your allocation size.

Using INT_MAX as infinity. dp[i - c] + 1 overflows when dp[i - c] == INT_MAX. Use 1e9 or add a guard: if (dp[i - c] < INF).

The INT_MAX overflow trap:

  dp[i-c] = INT_MAX = 2,147,483,647
                                  + 1
                      ─────────────────
                    = -2,147,483,648   <- WRAPPED TO NEGATIVE!

  min(dp[i], dp[i-c] + 1)
  min(dp[i], -2147483648)  <- picks the negative "minimum"

  Your DP now thinks an unreachable state is the best path.

  FIX: use INF = 1e9, or guard with:
    if (dp[i - c] < INF) dp[i] = min(dp[i], dp[i - c] + 1);

Forgetting modular arithmetic. Counting problems often need % 1e9+7. Apply mod at every addition, not just at the end, to avoid overflow:
cpp
```
const int MOD = 1e9 + 7;
dp[i] = (dp[i] + dp[i - c]) % MOD;
```
Combinations vs permutations loop order. Swapping the coin loop and amount loop changes whether {1,3} and {3,1} are counted as one way or two. See Pattern 4.
LIS: strict vs non-strict. lower_bound gives strictly increasing. upper_bound gives non-decreasing. Mixing these up is a classic bug.
Space blow-up on multiple test cases. If the problem has $t$ test cases, don't allocate a new vector each time -- fill or resize once with the max possible n.
Debugging tip: Print the entire dp array for a small example. Compare it with your hand-computed table. The first mismatch pinpoints the bug in your recurrence or base case.

Mental Traps

  TRAP: "1D DP is just for simple problems"

  Reality check:
  ┌──────────────────────────────┬──────────────┬──────────┐
  │  Problem                     │  Still 1D DP │  Trick   │
  ├──────────────────────────────┼──────────────┼──────────┤
  │  Fibonacci                   │      OK       │  none    │
  │  LIS (O(n log n))           │      OK       │  bin srch│
  │  Coin change (all variants) │      OK       │  loop ord│
  │  House robber + cooldown    │      OK       │  states  │
  │  Kadane with multiplier     │      OK       │  augment │
  └──────────────────────────────┴──────────────┴──────────┘
  "1D" = state has one index. Difficulty is unbounded.

Trap 1: "1D DP is just for simple problems." The "1D" describes the state space layout, not the conceptual difficulty. LIS with patience sorting, coin change counting with modular arithmetic, and Kadane variants with constraints are all 1D DPs that can appear at CF 1800+ ratings. Don't dismiss a problem as easy because you recognize the state as one-dimensional.

Trap 2: "Memoization is always correct if I memoize the right function." Memoization is correct only if the function is pure -- same inputs produce the same output every time. If your recursive function reads or writes any implicit state (global variables, mutable references not passed as parameters), memoization will cache results from one call path and serve them to a logically different call. The fix: make every piece of information the function depends on an explicit parameter.

Trap 3: "The transition I wrote is the only valid one." Most DPs can be written as either pull (compute dp[i] from earlier states) or push (from dp[i], update later states). They are equivalent, but one direction is often more natural or easier to optimize. When stuck on a transition, try writing it in the other direction -- clarity often follows.

  Pull vs Push -- two views of the same DP:

  PULL (standard):                 PUSH (alternative):
  for i = 1 to n:                  for i = 0 to n-1:
    for each transition t:           for each transition t:
      dp[i] = min(dp[i],              dp[i + t.step] = min(
                  dp[i - t.step]         dp[i + t.step],
                  + t.cost)              dp[i] + t.cost)

  <- reads from the past             -> writes to the future
  "Where could I have come from?"   "Where can I go from here?"

🐛 When Your Solution is Wrong

WA (Wrong Answer):
- Wrong base case (e.g., dp[0] = 0 vs dp[0] = 1 -- check what the empty case means)
- Iterating in wrong direction (bottom-up vs top-down mismatch)
- Wrong recurrence -- double-check by hand on small examples
TLE (Time Limit Exceeded):
- Not memoizing in top-down approach -> exponential recomputation
- State space too large -- look for ways to reduce dimensions
RE (Runtime Error):
- Stack overflow from deep recursion ( $n > 10^{5}$ ) -- switch to bottom-up
- Array index out of bounds (negative indices or off-by-one)

Common Mistakes

Wrong base case. Counting problems need dp[0] = 1 (one way to do nothing). Min-cost problems need dp[0] = 0. Swapping these silently gives wrong answers on every test.
Off-by-one on array size. dp needs size target + 1. Writing dp[target + 1] is undefined behavior.
INT_MAX as infinity. dp[i - c] + 1 wraps to negative when dp[i - c] == INT_MAX. Use 1e9 or guard with if (dp[i - c] < INF).
Top-down without memoization. Writing the recursion but forgetting the memo table gives correct but exponential-time results.
Space optimization breaking reconstruction. Rolling to O(1) space loses the DP table you need to backtrack the solution path.
Confusing permutation vs combination loop order. Coin change has two variants that differ by only loop nesting: for each sum, for each coin counts permutations (order matters), while for each coin, for each sum counts combinations (order doesn't). Mismatching the loop order to the problem's notion of "distinct" is the most common 1D DP bug.

Debug Drills

Drill 1. Climbing stairs -- but dp[2] returns 0.

cpp

int dp[105];
dp[0] = 1;
for (int i = 2; i <= n; i++)
    dp[i] = dp[i-1] + dp[i-2];

What's wrong?

dp[1] is never set -- it stays 0 (or garbage if uninitialized). Add dp[1] = 1; before the loop. Always initialize ALL base cases.

Drill 2. Maximum subarray sum returns 0 on an all-negative array.

cpp

int best = 0, cur = 0;
for (int i = 0; i < n; i++) {
    cur = max(0, cur + a[i]);
    best = max(best, cur);
}

What's wrong?

When all elements are negative, cur resets to 0 every step, so best stays 0. If the problem requires a non-empty subarray, initialize best = a[0] and cur = a[0], then use cur = max(a[i], cur + a[i]) starting from i = 1.

Drill 3. Coin change (minimum coins) returns 0 instead of -1 for impossible sums.

cpp

vector<int> dp(W + 1, INT_MAX);
dp[0] = 0;
for (int i = 1; i <= W; i++)
    for (int c : coins)
        if (i >= c)
            dp[i] = min(dp[i], dp[i - c] + 1);

What's wrong?

When dp[i - c] is INT_MAX, adding 1 causes integer overflow, wrapping to a large negative number. Guard with if (i >= c && dp[i - c] != INT_MAX). Alternatively, initialize with W + 1 instead of INT_MAX -- any unreachable state stays above W and can be detected.

Self-Test

Before moving to practice problems, verify you can:

[ ] Write the coin change (min coins) recurrence from scratch, including correct INF initialization
[ ] Explain why dp[0] = 1 for counting problems but dp[0] = 0 for min-cost problems
[ ] Implement LIS in $O (n^{2})$ and explain what dp[i] means precisely
[ ] State the difference between combination and permutation loop orderings for coin change
[ ] Convert a top-down memoized solution to bottom-up and vice versa
[ ] Identify when a 1D state is insufficient and a second dimension is needed
[ ] Debug a DP that gives wrong answers only on length-1 inputs (what's the likely cause?)

Practice Problems

CF Rating	How 1D DP Appears
1200	Fibonacci, staircase climbing, simple coin change
1500	Kadane's algorithm variants, DP with 2-3 states (e.g., "what did I do yesterday?")
1800	Segment DP with prefix sums, DP + greedy hybrid, non-obvious state definitions
2100	1D DP with data structure optimization (segment tree / deque for transitions)

#	Problem	Source	Difficulty	Key Idea
1	Cut Ribbon	CF 189A	Easy (1300)	Min/max DP with fixed step sizes
2	Kefa and First Steps	CF 580A	Easy (1000)	Longest non-decreasing contiguous subarray
3	Boredom	CF 455A	Easy (1500)	Take/skip DP on value frequencies
4	Basketball Exercise	CF 1195C	Easy (1400)	Two-row selection DP, alternating choices
5	Longest Increasing Subsequence	CSES	Medium	Classic LIS with $O (n \log n)$
6	Minimizing Coins	CSES	Easy	Coin change, minimum coins
7	Coin Combinations I	CSES	Easy	Count permutations (order matters)
8	Coin Combinations II	CSES	Easy	Count combinations (order doesn't matter)
9	Beautiful Array	CF 1155D	Medium (1900)	Kadane variant with a multiplier segment
10	Vacations	CF 698A	Medium (1400)	State DP: track what you did yesterday

Code Reading Exercise

What does this code compute? Read it carefully before checking the answer.

cpp

int solve(string& s) {
    int n = s.size();
    vector<int> dp(n + 1, 0);
    dp[0] = 1;
    for (int i = 1; i <= n; i++) {
        if (s[i - 1] != '0')
            dp[i] += dp[i - 1];
        if (i >= 2 && s[i - 2] != '0') {
            int two = (s[i - 2] - '0') * 10 + (s[i - 1] - '0');
            if (two <= 26) dp[i] += dp[i - 2];
        }
    }
    return dp[n];
}

Answer
This counts the number of ways to decode a digit string into letters, where 'A' = 1, 'B' = 2, ..., 'Z' = 26. Each digit can be decoded as a single letter (if non-zero), and two consecutive digits can form one letter (if the value is 1-26). dp[i] = number of valid decodings of s[0..i-1]. The two transitions correspond to using the last one or two digits. This is the classic "Decode Ways" problem.

What does this code compute?

cpp

bool solve(vector<int>& a) {
    int total = 0;
    for (int x : a) total += x;
    if (total % 2 != 0) return false;
    int half = total / 2;
    vector<bool> dp(half + 1, false);
    dp[0] = true;
    for (int x : a)
        for (int j = half; j >= x; j--)
            dp[j] = dp[j] || dp[j - x];
    return dp[half];
}

Answer
This determines whether the array can be partitioned into two subsets with equal sum. It reduces to 0/1 knapsack: can we select a subset summing to total/2? The key detail is the reverse iteration (j from half down to x) -- this ensures each element is used at most once per subset. dp[j] is true if some subset of the processed elements sums to exactly j. If total is odd, no partition exists.

Reconstruct It

Setup: You have a recursive solution to a problem (e.g., Fibonacci, staircase climbing, grid paths). It works correctly but is far too slow -- it times out even on moderate inputs.
You suspect it's recomputing the same subproblems many times. How do you eliminate the redundant work?

Constraint hint: Draw the recursion tree. If the same function call (same arguments) appears in multiple branches, you're doing duplicate work.

Step 1 -- Identify the overlap. Take fib(5): it calls fib(4) and fib(3). But fib(4) also calls fib(3). So fib(3) is computed twice -- and the duplication grows exponentially. There are only $O (n)$ distinct subproblems, but the naive tree has $O (2^{n})$ nodes.

Step 2 -- Memoize (top-down). Before computing f(x), check if you've already stored the result. If yes, return it immediately. If no, compute it, store it, then return. This turns the exponential tree into a DAG with $O (n)$ nodes -- each subproblem solved exactly once.

Step 3 -- Tabulate (bottom-up). Instead of recursing, fill a table iteratively from the smallest subproblem up. dp[0] = base, dp[1] = base, then dp[i] = dp[i-1] + dp[i-2]. No recursion overhead, no stack depth issues, and the loop order guarantees dependencies are ready.

Full derivation

From recursion to DP in three stages:

Write the recurrence. Express the answer to the full problem in terms of smaller subproblems: f(n) = f(n-1) + f(n-2), with base cases f(0) = 0, f(1) = 1.
Add memoization. Create a cache (hash map or array). At the start of f(x), check the cache. At the end, store the result before returning. Time drops from $O (2^{n})$ to $O (n)$ -- each of the $n$ subproblems is computed once, and each takes $O (1)$ work.
Convert to bottom-up. Determine a valid fill order (here, increasing $i$ ). Allocate dp[0..n]. Fill base cases. Loop from i = 2 to n: dp[i] = dp[i-1] + dp[i-2]. If only the last few entries are needed (as here), optimize space to $O (1)$ by keeping just two variables.

This is the essence of dynamic programming: recursion + memoization = top-down DP, and iterative table-filling = bottom-up DP. Both eliminate redundant subproblem computation. Bottom-up often has better constant factors and avoids stack overflow.

Recap

1D DP reduces to: define dp[i], write recurrence, set base case, fill left to right.
Top-down (memoization) and bottom-up (tabulation) are equivalent; bottom-up avoids stack overflow and typically has better constants.
Space optimization: if dp[i] depends only on dp[i-1] and dp[i-2], keep two variables instead of an array.
Recognition pattern: the problem gives a sequence and asks for a count, min-cost, or max-value that decomposes into prefix subproblems.

Cross-Links

DP Thinking Framework -- systematic state design for harder DP problems
DP -- Knapsack -- extends 1D DP with a capacity constraint
DP vs Greedy Guide -- when greedy suffices and when you need DP
DP Practice Ladder -- graded problem set

Dynamic Programming -- 1D Introduction ​

Contents ​

Intuition ​

Visual Walkthrough ​

The Invariant ​

What the Code Won't Teach You ​

When to Reach for This ​

C++ STL Reference ​

Implementation (Contest-Ready) ​

Version 1: Coin Change -- Minimum Coins (Minimal) ​

Version 1: Coin Change -- Explained ​

Version 2: Longest Increasing Subsequence -- O(n2) (Minimal) ​

Version 2: LIS -- Explained ​

Bonus: LIS in O(nlog⁡n) -- Patience Sorting ​

Operations Reference ​

Problem Patterns & Tricks ​

Pattern 1: Staircase / Path Counting ​

Pattern 2: Minimum / Maximum Cost ​

Pattern 3: Longest Increasing Subsequence (LIS) ​

Pattern 4: Coin Change / Knapsack Variants ​

Pattern 5: State Reduction / Space Optimization ​

Pattern 6: Kadane's Algorithm (Max Subarray) ​

Contest Cheat Sheet ​

Gotchas & Debugging ​

Mental Traps ​

🐛 When Your Solution is Wrong ​

Common Mistakes ​

Debug Drills ​

Self-Test ​

Practice Problems ​

Further Reading ​

Code Reading Exercise ​

Reconstruct It ​

Recap ​

Cross-Links ​

Dynamic Programming -- 1D Introduction

Contents

Intuition

Visual Walkthrough

The Invariant

What the Code Won't Teach You

When to Reach for This

C++ STL Reference

Implementation (Contest-Ready)

Version 1: Coin Change -- Minimum Coins (Minimal)

Version 1: Coin Change -- Explained

Version 2: Longest Increasing Subsequence -- $O (n^{2})$ (Minimal)

Version 2: LIS -- Explained

Bonus: LIS in $O (n \log n)$ -- Patience Sorting

Operations Reference

Problem Patterns & Tricks

Pattern 1: Staircase / Path Counting

Pattern 2: Minimum / Maximum Cost

Pattern 3: Longest Increasing Subsequence (LIS)

Pattern 4: Coin Change / Knapsack Variants

Pattern 5: State Reduction / Space Optimization

Pattern 6: Kadane's Algorithm (Max Subarray)

Contest Cheat Sheet

Gotchas & Debugging

Mental Traps

🐛 When Your Solution is Wrong

Common Mistakes

Debug Drills

Self-Test

Practice Problems

Further Reading

Code Reading Exercise

Reconstruct It

Recap

Cross-Links