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
- State: what does dp[...] mean, in words? (best after day i with run k)
- Transitions: how is each state built from others? (rest / open after rest / open again)
- Base case: where do you start? Impossible states get −∞ (for max) or +∞ (for min).
- Order: fill so every input is ready (i = 1, 2, …, n).
- 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
-
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>. -
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). -
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). -
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
- What is a DP state? A minimal description of a subproblem: everything the remaining decisions depend on, and nothing more.
- 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.
- How do you estimate DP complexity? Number of states × transitions per state.
- 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.
- 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.
- 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 (
4vs202); 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:
intsums (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.