SyntaxPilot
Courses/Competitive Programming/Lesson 32

Competitive Programming · Lesson 32 of 90 · 11 min

DP for contests 1: states and transitions

queued

These are the notes for Competitive Programming episode 32, the start of the dynamic programming section. Ramesh's chai stall earns a different amount every day but can never open three days in a row. An original problem, Chai Stall Plan, asks for the best total. The greedy plan "open whenever allowed" prints 4 instead of 202; trying all 2^n plans is right but gets TLE at 40 days. The key question is what the future needs to remember: only the day and how many days in a row the stall has just been open. That pair is the state, rest/open are the transitions, and each state is solved once, either top-down (recursion + memo) or bottom-up (a table). The episode ends with the five-step DP checklist (state, transitions, base case, order, answer) and the rule time = states × transitions. Every C++ example was compiled with g++ -O2 -std=c++17 main.cpp -o main (g++ 13, the same command as the SyntaxPilot compiler); all outputs below are real.

The real-life hook

Ramesh's chai stall near the station: he knows each day's earnings in advance (festival days pay ₹100, ordinary days ₹1), but after two open days he must rest. Which days should he open? Today's choice changes tomorrow's options, which is exactly when greedy breaks and DP is needed.

Problem I · Chai Stall Plan

(Written for this course, in the style of an AtCoder Beginner Contest problem.)

n days. If the stall is open on day i, Ramesh earns ai. He may never be open on three consecutive days. Print the maximum total.

  • Input: n (1 ≤ n ≤ 2 · 10^5), then a1 … an (0 ≤ ai ≤ 10^9).
  • Output: the maximum total.
Input Output
6 / 1 1 100 1 1 100 202 (open days 2, 3, 5, 6)
5 / 10 20 30 40 50 120 (rest on day 3)
7 / 3 8 2 9 4 7 6 33

Attempt 1: greedy (wrong)

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

int main() {
    int n;
    cin >> n;
    vector<ll> a(n);
    for (ll &x : a) cin >> x;
    ll total = 0;
    int run = 0;                 // open days in a row
    for (int i = 0; i < n; i++) {
        if (run < 2) { total += a[i]; run++; }   // open if allowed
        else run = 0;                                // forced rest
    }
    cout << total << "\n";
    return 0;
}

Output on sample 1: 4 (expected 202). Greedy opens on the two ₹1 days, then is forced to rest on the ₹100 festival day, twice.

Attempt 2: all 2^n plans (Time Limit Exceeded)

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

int main() {
    int n;
    cin >> n;
    vector<ll> a(n);
    for (ll &x : a) cin >> x;
    ll best = 0;
    for (ll m = 0; m < (1LL << n); m++) {   // bit i: open on day i
        bool ok = true;
        ll sum = 0;
        for (int i = 0; i < n; i++) {
            if (!(m >> i & 1)) continue;
            sum += a[i];
            if (i >= 2 && (m >> (i - 1) & 1) && (m >> (i - 2) & 1)) ok = false;
        }
        if (ok) best = max(best, sum);
    }
    cout << best << "\n";
    return 0;
}

Samples: 202, 120, 33 ✓. With 40 days: Time Limit Exceeded (2^40 ≈ 1.1 · 10^12 plans, each checked in O(n)).

The key question: what does the future need to know?

Two different histories, open-rest-open-open and rest-open-rest-open-open, both end with two open days in a row. From here on they have exactly the same choices and the same future earnings. The future only needs:

  • i: which day it is;
  • run: how many days in a row the stall has just been open (0, 1 or 2).

That pair is the state: the smallest summary of the past that the future needs. 2^n histories collapse into 3n states.

Real life DP
a bookmark saves the page, not every page you read state = (day, run)
each turn on a road trip takes you to the next town transition = rest or open
write an answer down so you never work it out twice memoisation

Top-down: recursion + memo

best(i, run) = the most Ramesh can still earn from day i on, having just been open run days in a row.

best(n, run) = 0                                   (no days left)
best(i, run) = max( best(i+1, 0),                  rest today
                    a[i] + best(i+1, run+1) )      open today, only if run < 2
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int n;
vector<ll> a;
vector<array<ll, 3>> memo;
vector<array<bool, 3>> done;

ll best(int i, int run) {          // days i..n-1, run open days just before i
    if (i == n) return 0;
    if (done[i][run]) return memo[i][run];
    ll res = best(i + 1, 0);              // rest today
    if (run < 2) res = max(res, a[i] + best(i + 1, run + 1));   // open today
    done[i][run] = true;
    return memo[i][run] = res;
}

int main() {
    cin >> n;
    a.resize(n);
    for (ll &x : a) cin >> x;
    memo.resize(n);
    done.assign(n, {false, false, false});
    cout << best(0, 0) << "\n";
    return 0;
}

Sample 1 → 202; the 40 days that timed out → 139, instantly (3 · 40 = 120 states, each solved once).

Without the two done/memo lines the same recursion prints 202 on sample 1 but gets Time Limit Exceeded on the 40 days.

Overlapping subproblems: without the memo, the same (i, run) is reached through many different histories and recomputed each time (exponential). With it, each state is computed once.

Bottom-up: the DP table

dp[i][k] = the best total after day i, with the stall open on the last k days in a row (k = 0, 1, 2).

dp[0]    = {0, −∞, −∞}                     before day 1: nothing open yet
dp[i][0] = max(dp[i−1][0], dp[i−1][1], dp[i−1][2])   rest on day i
dp[i][1] = dp[i−1][0] + a[i]                         open after a rest
dp[i][2] = dp[i−1][1] + a[i]                         second open day in a row
answer   = max(dp[n][0], dp[n][1], dp[n][2])

Sample 3 (3 8 2 9 4 7 6):

day 0 1 2 3 4 5 6 7
earn 3 8 2 9 4 7 6
run 0 0 0 3 11 11 20 24 27
run 1 −∞ 3 8 5 20 15 27 30
run 2 −∞ −∞ 11 10 14 24 22 33

Each column needs only the previous one, so the table can even be replaced by three variables (see the stress test).

Why −∞ for impossible states? Before day 1 you can't have been open for 1 or 2 days. If those cells were 0, a max could pick them as if they were real totals. −∞ (here LLONG_MIN / 4, so adding 10^9 can't overflow) makes sure they are never chosen.

The DP checklist

  1. State: what does dp[...] mean, in words? (best after day i with run k)
  2. Transitions: how is each state built from others? (rest / open after rest / open again)
  3. Base case: where do you start? Impossible states get −∞ (for max) or +∞ (for min).
  4. Order: fill so every input is ready (i = 1, 2, …, n).
  5. Answer: which cell or cells? (max of the last column)

Time = number of states × work per state: 3n states × O(1) = O(n). Memory O(n), or O(1) with rolling variables.

Top-down or bottom-up?

Top-down (memo) Bottom-up (table)
How recursion + memo loops in dependency order
States computed only the reachable ones all of them
Risk deep recursion (n ≈ 10^6) can overflow the stack none
Contest habit think in it submit it

The accepted solution

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    vector<ll> a(n);
    for (ll &x : a) cin >> x;
    const ll NEG = LLONG_MIN / 4;          // "impossible"
    vector<array<ll, 3>> dp(n + 1, {NEG, NEG, NEG});
    dp[0] = {0, NEG, NEG};                // before day 1: run = 0
    for (int i = 1; i <= n; i++) {
        ll x = a[i - 1];
        dp[i][0] = max({dp[i - 1][0], dp[i - 1][1], dp[i - 1][2]});   // rest
        dp[i][1] = dp[i - 1][0] + x;      // open after a rest
        dp[i][2] = dp[i - 1][1] + x;      // second open day in a row
    }
    cout << max({dp[n][0], dp[n][1], dp[n][2]}) << "\n";
    return 0;
}
Input Output
sample 1 202
sample 3 33
1 / 7 7
worst case (below) 133334000000000

The worst case, built inside main (2 · 10^5 days of 10^9 each):

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

int main() {
    int n = 200000;                        // worst case, built here
    vector<ll> a(n, 1000000000);
    const ll NEG = LLONG_MIN / 4;          // "impossible"
    vector<array<ll, 3>> dp(n + 1, {NEG, NEG, NEG});
    dp[0] = {0, NEG, NEG};                // before day 1: run = 0
    for (int i = 1; i <= n; i++) {
        ll x = a[i - 1];
        dp[i][0] = max({dp[i - 1][0], dp[i - 1][1], dp[i - 1][2]});   // rest
        dp[i][1] = dp[i - 1][0] + x;      // open after a rest
        dp[i][2] = dp[i - 1][1] + x;      // second open day in a row
    }
    cout << max({dp[n][0], dp[n][1], dp[n][2]}) << "\n";
    return 0;
}

Output: 133334000000000 (open 2 days out of every 3: 133,334 days × 10^9), instantly. It does not fit in an int.

A stress test

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

ll brute(vector<ll>& a) {             // all 2^n plans
    int n = a.size();
    ll best = 0;
    for (int m = 0; m < (1 << n); m++) {
        if (m & (m >> 1) & (m >> 2)) continue;   // 3 in a row
        ll sum = 0;
        for (int i = 0; i < n; i++) if (m >> i & 1) sum += a[i];
        best = max(best, sum);
    }
    return best;
}
ll fast(vector<ll>& a) {              // the DP, with 3 numbers
    const ll NEG = LLONG_MIN / 4;
    ll d0 = 0, d1 = NEG, d2 = NEG;
    for (ll x : a) { ll n0 = max({d0, d1, d2}); d2 = d1 + x; d1 = d0 + x; d0 = n0; }
    return max({d0, d1, d2});
}
int main() {
    mt19937 rng(32);
    for (int t = 1; t <= 1000; t++) {
        vector<ll> a(rng() % 15 + 1);
        for (ll &x : a) x = rng() % 100;
        if (brute(a) != fast(a)) { cout << "mismatch on test " << t; return 0; }
    }
    cout << "all 1000 tests passed";
}

Output: all 1000 tests passed. Note the trick m & (m >> 1) & (m >> 2): it is non-zero exactly when the mask has three 1 bits in a row.

Complexity vs the constraints

Method Time n = 2 · 10^5
all plans O(2^n · n) TLE at n = 40
greedy O(n) fast, but wrong (4 vs 202)
DP over (i, run) O(3n) ≈ 6 · 10^5 steps

Common mistakes (and the real outputs)

Bug 1: int sums

The worst case with vector<int> a, array<int, 3> and INT_MIN / 4:

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

int main() {
    int n = 200000;                        // worst case, built here
    vector<int> a(n, 1000000000);
    const int NEG = INT_MIN / 4;          // "impossible"
    vector<array<int, 3>> dp(n + 1, {NEG, NEG, NEG});
    dp[0] = {0, NEG, NEG};                // before day 1: run = 0
    for (int i = 1; i <= n; i++) {
        int x = a[i - 1];
        dp[i][0] = max({dp[i - 1][0], dp[i - 1][1], dp[i - 1][2]});   // rest
        dp[i][1] = dp[i - 1][0] + x;      // open after a rest
        dp[i][2] = dp[i - 1][1] + x;      // second open day in a row
    }
    cout << max({dp[n][0], dp[n][1], dp[n][2]}) << "\n";
    return 0;
}

Output: 2000000000 (expected 133334000000000). The sums pass 2^31 − 1 ≈ 2.1 · 10^9 and overflow (undefined behaviour), so the result is garbage.

Bug 2: reading the wrong answer cell

    cout << dp[n][0] << "\n";          // the last cell?

Output on sample 1: 102 (expected 202). dp[n][0] means "resting on the last day", but the best plan opens on the last festival day. The answer is the max over the last column.

Summary table

Mistake What you see Why Fix
open whenever allowed (greedy) 4 instead of 202 today's choice changes tomorrow DP over states
vector<array<int, 3>> dp 2000000000 the total passes 2^31 long long
cout << dp[n][0]; 102 instead of 202 the best plan may end open max over the last column
dp[0] = {0, 0, 0}; impossible states can be chosen 0 is a real total −∞ for impossible states
recursion without memo TLE the same state is solved many times memo table

Mini project

Write one program that solves Chai Stall Plan four ways (greedy, 2^n brute force, top-down memo, bottom-up with three rolling variables), runs all of them on 1000 random small inputs, and prints which ones disagree with the brute force. Then extend the DP to print the actual open days (store, for each state, which transition gave the max, and walk back from the answer cell).

Practice

  1. Never k days in a row (k ≤ 10).

    Answer State run = 0 … k − 1: dp[i][0] = max of the previous column, dp[i][r] = dp[i−1][r−1] + a[i] for 1 ≤ r ≤ k − 1. O(nk). With k = 4 (never 4 in a row): sample 3 → <b>33</b>, sample 1 → <b>203</b>.

  2. Rest days cost ₹c (rent is paid even when closed).

    Answer Same states; the rest transition adds −c: dp[i][0] = max(previous column) − c. Sample 1 with c = 1 → <b>200</b>; sample 3 with c = 5 → <b>23</b> (checked by brute force).

  3. Count the valid plans mod 10^9 + 7.

    Answer Replace max by + and earnings by 1: cnt[i][0] = sum of the previous column, cnt[i][1] = cnt[i−1][0], cnt[i][2] = cnt[i−1][1]. n = 1 … 10: 2, 4, 7, 13, 24, 44, 81, 149, 274, <b>504</b> (episode 29's Rangoli numbers again, shifted).

  4. Print which days to open for sample 1.

    Answer Store the choice for each state, then walk back from the best cell of the last column: days <b>2, 3, 5, 6</b> (1 + 100 + 1 + 100 = 202).

Quick quiz

New rule: never open 4 days in a row. How many states per day?

A) 2 · B) 3 · C) 4 · D) 2^4

Answer

C. The run can be 0, 1, 2 or 3 open days. 4n states, still O(n).

Interview questions

  1. What is a DP state? A minimal description of a subproblem: everything the remaining decisions depend on, and nothing more.
  2. Top-down vs bottom-up? Top-down: recursion + memo, computes only reachable states, easy to write. Bottom-up: loops over a table in dependency order, no recursion overhead or stack limits, easy to optimise memory.
  3. How do you estimate DP complexity? Number of states × transitions per state.
  4. When does greedy fail and DP work? When a choice now changes which choices are available later, and the locally best choice can block a better future.
  5. What are overlapping subproblems and optimal substructure? The same subproblem appears many times; the best answer is built from the best answers of subproblems. Together they make DP work.
  6. How do you handle impossible states? Initialise them to −∞ for maximisation (+∞ for minimisation) so they are never chosen.

Glossary

Term Meaning Example
Dynamic programming (DP) Solve each subproblem once, build bigger answers from smaller ones the stall table
State What the future needs to know (day i, run k)
Transition How a state is built from other states rest / open
Base case The starting state(s) dp[0] = {0, −∞, −∞}
Memoisation (memo) Storing results so each state is computed once memo[i][run]
Top-down Recursion + memo best(i, run)
Bottom-up (tabulation) Filling a table in order for i = 1 … n
Overlapping subproblems The same subproblem reached many ways many histories → (i, 2)
Optimal substructure The best answer uses best answers of parts best total from day i
−∞ sentinel A value meaning "impossible" for max LLONG_MIN / 4
Greedy Take the locally best choice open whenever allowed
Bitmask An integer whose bits encode a subset bit i = open on day i
Stress test Fast vs brute force on random small tests all 1000 tests passed
Integer overflow A value exceeds its type's range 2000000000

Summary

  • Greedy fails when today's choice changes tomorrow (4 vs 202); all 2^n plans TLE at n = 40.
  • Ask what the future needs: state = (day, run), 3n states instead of 2^n histories.
  • Transitions: rest → run 0; open → run + 1 (if run < 2). Base: {0, −∞, −∞}. Answer: max of the last column.
  • Top-down (memo) and bottom-up (table) solve each state once: time = states × transitions = O(n).
  • Real bugs: int sums (2000000000), reading only dp[n][0] (102).

Solutions in C++, Java and Python

Problem I · Chai Stall Plan

C++: see "The accepted solution" above.

Java:

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder all = new StringBuilder();
        String line;
        while ((line = br.readLine()) != null) all.append(line).append(' ');
        StringTokenizer in = new StringTokenizer(all.toString());
        int n = Integer.parseInt(in.nextToken());
        final long NEG = Long.MIN_VALUE / 4;
        long d0 = 0, d1 = NEG, d2 = NEG;                // run 0, 1, 2
        for (int i = 0; i < n; i++) {
            long x = Long.parseLong(in.nextToken());
            long n0 = Math.max(d0, Math.max(d1, d2));     // rest
            long n1 = d0 + x;                             // open after a rest
            long n2 = d1 + x;                             // open again
            d0 = n0; d1 = n1; d2 = n2;
        }
        System.out.println(Math.max(d0, Math.max(d1, d2)));
    }
}

Python:

import sys

data = sys.stdin.buffer.read().split()
n = int(data[0])
NEG = float("-inf")
d0, d1, d2 = 0, NEG, NEG                  # run 0, 1, 2
for x in map(int, data[1:n + 1]):
    d0, d1, d2 = max(d0, d1, d2), d0 + x, d1 + x
print(max(d0, d1, d2))

All three print 202, 120 and 33 on the samples.