These are the notes for Competitive Programming episode 35, part four of the dynamic programming section. At closing time a sweet shop has a row of laddoo trays; the helper can only merge two neighbouring trays and charges one rupee per laddoo he lifts. An original problem, Laddoo Trays, asks for the cheapest way to end with one tray. Greedy "merge the cheapest pair" prints 150 instead of 140; trying every merge order is right but gets TLE at 13 trays. The key is to think about the last merge: it joins a left block l..k and a right block k+1..r that were merged independently. The state is a range, dp[l][r]; the transition tries every split point k and adds the range sum (from prefix sums); the table is filled by length, short ranges first. O(n³). 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
A row of laddoo trays: 20, 20, 10, 20. The trays are too heavy to reorder, so only neighbours can be merged, and the helper charges ₹1 per laddoo lifted (both trays are lifted). Merging the two 20s costs 40. What order of merges is cheapest? The same shape hides in many problems: multiplying a chain of matrices, combining files, bracketing an expression, popping balloons, removing palindromes.
Problem L · Laddoo Trays
(Written for this course, in the style of an AtCoder Beginner Contest problem.)
n trays stand in a row; tray i holds ai laddoos. Repeatedly merge two neighbouring trays into one; a merge costs the total number of laddoos in the two trays. Continue until one tray is left. Print the minimum total cost.
- Input: n (1 ≤ n ≤ 400), then a1 … an (1 ≤ ai ≤ 10^9).
- Output: the minimum total cost.
| Input | Output |
|---|---|
4 / 20 20 10 20 |
140 ((20+20) = 40, (10+20) = 30, then 70) |
4 / 10 20 30 40 |
190 |
1 / 7 |
0 |
Attempt 1: merge the cheapest neighbouring pair (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 cost = 0;
while (a.size() > 1) {
int best = 0; // cheapest neighbouring pair
for (int i = 0; i + 1 < (int)a.size(); i++)
if (a[i] + a[i + 1] < a[best] + a[best + 1]) best = i;
a[best] += a[best + 1];
cost += a[best];
a.erase(a.begin() + best + 1);
}
cout << cost << "\n";
return 0;
}
Sample 1 prints 150 (expected 140). Greedy merges 20 + 10 first (30 is the cheapest pair), leaving 20, 30, 20; then 20 + 30 = 50 and finally 70: 30 + 50 + 70 = 150. The better plan pays 40 + 30 + 70 = 140. Cheap now, expensive later.
Attempt 2: every merge order (Time Limit Exceeded)
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
ll solve(vector<ll> a) { // try every next merge
if (a.size() == 1) return 0;
ll best = LLONG_MAX;
for (int i = 0; i + 1 < (int)a.size(); i++) {
vector<ll> b = a;
b[i] += b[i + 1];
b.erase(b.begin() + i + 1);
best = min(best, b[i] + solve(b));
}
return best;
}
int main() {
int n;
cin >> n;
vector<ll> a(n);
for (ll &x : a) cin >> x;
cout << solve(a) << "\n";
return 0;
}
Samples: 140, 190, correct. With 13 trays it prints Time Limit Exceeded: (n − 1)! = 12! ≈ 4.8 · 10^8 merge orders, each copying a vector.
The key observation: think about the LAST merge
The first merge has n − 1 choices, and after it the row changes, so the choices tangle together. Flip it: at the very end exactly two trays remain. One was made from a left block l..k, the other from a right block k+1..r. Those blocks never interacted: each was merged on its own. So each is the same problem on a shorter range. And the last merge lifts every laddoo in l..r, so it costs sum(l..r), whatever k is.
State: dp[l][r] = the cheapest way to merge trays l..r into one.
Transition: dp[l][r] = min over k in [l, r) of (dp[l][k] + dp[k+1][r]) + sum(l..r).
Base: dp[i][i] = 0 (one tray, nothing to merge). Answer: dp[0][n−1].
Two tools: prefix sums and the fill order
- Range sums in O(1) (episode 7): pre[i] = a[0] + … + a[i−1], so sum(l..r) = pre[r+1] − pre[l].
- Fill order: dp[l][r] reads dp[l][k] and dp[k+1][r], both shorter ranges. So the outer loop is the length (2 … n), and the inner loop is the start l, with r = l + len − 1. (Running l from n − 1 down to 0, with r going up, also works.)
About n²/2 states, up to n splits each: n³/6 ≈ 1.1 · 10^7 steps for n = 400.
The table on sample 2 (10 20 30 40)
| length | l = 0 | l = 1 | l = 2 | l = 3 |
|---|---|---|---|---|
| 1 | 0 | 0 | 0 | 0 |
| 2 | 30 | 50 | 70 | |
| 3 | 90 | 140 | ||
| 4 | 190 |
- dp[0][2] (10 20 30) = min(0 + 50, 30 + 0) + 60 = 90.
- dp[1][3] (20 30 40) = min(0 + 70, 50 + 0) + 90 = 140.
- dp[0][3] = min(0 + 140, 30 + 70, 90 + 0) + 100 = 190.
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;
vector<ll> pre(n + 1, 0); // pre[i] = a[0] + ... + a[i-1]
for (int i = 0; i < n; i++) pre[i + 1] = pre[i] + a[i];
// dp[l][r] = cheapest way to merge trays l..r into one
vector<vector<ll>> dp(n, vector<ll>(n, 0));
for (int len = 2; len <= n; len++) // short ranges first
for (int l = 0; l + len - 1 < n; l++) {
int r = l + len - 1;
dp[l][r] = LLONG_MAX;
for (int k = l; k < r; k++) // last merge: [l..k] + [k+1..r]
dp[l][r] = min(dp[l][r], dp[l][k] + dp[k + 1][r]);
dp[l][r] += pre[r + 1] - pre[l]; // the last merge lifts every laddoo
}
cout << dp[0][n - 1] << "\n";
return 0;
}
| Input | Output |
|---|---|
| sample 1 | 140 |
| sample 2 | 190 |
1 / 7 |
0 |
| the 13-tray test that timed out | 249 (instant) |
The worst case, built inside main (400 trays of 10^9):
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {
int n = 400; // worst case, built here
vector<ll> a(n, 1000000000);
vector<ll> pre(n + 1, 0); // pre[i] = a[0] + ... + a[i-1]
for (int i = 0; i < n; i++) pre[i + 1] = pre[i] + a[i];
// dp[l][r] = cheapest way to merge trays l..r into one
vector<vector<ll>> dp(n, vector<ll>(n, 0));
for (int len = 2; len <= n; len++) // short ranges first
for (int l = 0; l + len - 1 < n; l++) {
int r = l + len - 1;
dp[l][r] = LLONG_MAX;
for (int k = l; k < r; k++) // last merge: [l..k] + [k+1..r]
dp[l][r] = min(dp[l][r], dp[l][k] + dp[k + 1][r]);
dp[l][r] += pre[r + 1] - pre[l]; // the last merge lifts every laddoo
}
cout << dp[0][n - 1] << "\n";
return 0;
}
Output: 3488000000000 (about 3.5 · 10^12), far past an int.
A stress test
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
ll brute(vector<ll> a) {
if (a.size() == 1) return 0;
ll best = LLONG_MAX;
for (int i = 0; i + 1 < (int)a.size(); i++) {
vector<ll> b = a;
b[i] += b[i + 1];
b.erase(b.begin() + i + 1);
best = min(best, b[i] + brute(b));
}
return best;
}
ll fast(vector<ll>& a) {
int n = a.size();
vector<ll> pre(n + 1, 0);
for (int i = 0; i < n; i++) pre[i + 1] = pre[i] + a[i];
vector<vector<ll>> dp(n, vector<ll>(n, 0));
for (int len = 2; len <= n; len++)
for (int l = 0, r = len - 1; r < n; l++, r++) {
dp[l][r] = LLONG_MAX;
for (int k = l; k < r; k++) dp[l][r] = min(dp[l][r], dp[l][k] + dp[k + 1][r]);
dp[l][r] += pre[r + 1] - pre[l];
}
return dp[0][n - 1];
}
int main() {
mt19937 rng(35);
for (int t = 1; t <= 1000; t++) {
vector<ll> a(rng() % 7 + 1);
for (ll &x : a) x = rng() % 50 + 1;
if (brute(a) != fast(a)) { cout << "mismatch on test " << t; return 0; }
}
cout << "all 1000 tests passed";
}
Output: all 1000 tests passed.
Same shape: a chain of matrices
Multiplying a p×q matrix by a q×r one takes p·q·r multiplications, and a product of several matrices can be bracketed in any order. A (10×30) · B (30×5) · C (5×60): (A·B)·C costs 1500 + 3000 = 4500, but A·(B·C) costs 9000 + 18000 = 27000. It is the same interval DP: the last multiplication joins (l..k) and (k+1..r), and costs d[l]·d[k+1]·d[r+1] (matrix i is d[i] × d[i+1]).
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {
int n; // n matrices
cin >> n;
vector<ll> d(n + 1); // matrix i is d[i] x d[i+1]
for (ll &x : d) cin >> x;
// dp[l][r] = cheapest way to multiply matrices l..r
vector<vector<ll>> dp(n, vector<ll>(n, 0));
for (int len = 2; len <= n; len++)
for (int l = 0; l + len - 1 < n; l++) {
int r = l + len - 1;
dp[l][r] = LLONG_MAX;
for (int k = l; k < r; k++) // last multiply: (l..k) x (k+1..r)
dp[l][r] = min(dp[l][r], dp[l][k] + dp[k + 1][r] + d[l] * d[k + 1] * d[r + 1]);
}
cout << dp[0][n - 1] << "\n";
return 0;
}
Input 3 / 10 30 5 60 → 4500.
Complexity vs the constraints
| Approach | Time | Verdict |
|---|---|---|
| every merge order | O((n − 1)! · n) | TLE at n = 13 |
| cheapest pair first | O(n²) | wrong (150 vs 140) |
| dp[l][r] with a loop for each range sum | O(n⁴) ≈ 10^9 | too slow |
| dp[l][r] + prefix sums, by length | O(n³ / 6) ≈ 1.1 · 10^7 | accepted |
Common mistakes (and the real outputs)
Bug 1: the wrong fill order
#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;
vector<ll> pre(n + 1, 0);
for (int i = 0; i < n; i++) pre[i + 1] = pre[i] + a[i];
vector<vector<ll>> dp(n, vector<ll>(n, 0));
for (int l = 0; l < n; l++) // row by row?
for (int r = l + 1; r < n; r++) {
dp[l][r] = LLONG_MAX;
for (int k = l; k < r; k++)
dp[l][r] = min(dp[l][r], dp[l][k] + dp[k + 1][r]);
dp[l][r] += pre[r + 1] - pre[l];
}
cout << dp[0][n - 1] << "\n";
return 0;
}
On sample 2 it prints 100 (expected 190). For l = 0 the code reads dp[k+1][r], rows that are filled later; they are still 0, so the right block looks free. Fill by length (or run l backwards).
Bug 2: int prefix sums
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {
int n = 400; // worst case, built here
vector<ll> a(n, 1000000000);
vector<int> pre(n + 1, 0); // int is enough?
for (int i = 0; i < n; i++) pre[i + 1] = pre[i] + a[i];
// dp[l][r] = cheapest way to merge trays l..r into one
vector<vector<ll>> dp(n, vector<ll>(n, 0));
for (int len = 2; len <= n; len++) // short ranges first
for (int l = 0; l + len - 1 < n; l++) {
int r = l + len - 1;
dp[l][r] = LLONG_MAX;
for (int k = l; k < r; k++) // last merge: [l..k] + [k+1..r]
dp[l][r] = min(dp[l][r], dp[l][k] + dp[k + 1][r]);
dp[l][r] += pre[r + 1] - pre[l]; // the last merge lifts every laddoo
}
cout << dp[0][n - 1] << "\n";
return 0;
}
On the worst case it prints -187768712704: a negative cost. Three trays of 10^9 already pass 2^31 − 1 ≈ 2.1 · 10^9, so the int prefix sums overflow and every range sum after that is garbage.
Summary table
| Mistake | What you see | Why | Fix |
|---|---|---|---|
| merge the cheapest pair | 150 instead of 140 |
cheap now, expensive later | DP on the last merge |
for l = 0..n, r = l+1..n |
100 instead of 190 |
reads unfilled cells | loop len outside (or l down) |
vector<int> pre |
-187768712704 |
sums pass 2^31 | long long |
| sum(l..r) with a loop at every split | O(n⁴): TLE | recomputes each sum | prefix sums |
forgetting + sum(l..r) |
far too small | the last merge is free | add the range sum once per state |
Mini project
Write a "merge planner": solve Laddoo Trays with the interval DP and also store cut[l][r], the best split point. Then print the merge plan as a bracketed expression by recursion: print(l, r) prints a[l] if l = r, otherwise ( + print(l, cut) + + + print(cut + 1, r) + ). For sample 1 it should show the two 20s merged first: ((20 + 20) + (10 + 20)).
Practice
-
The trays stand in a circle (tray n is next to tray 1).
Answer
Write the array twice (length 2n), run the same DP on ranges of length up to n, and take the minimum of dp[i][i+n−1] over i. Same O(n³) with a constant factor of 8. <code>10 40 40 10</code>: in a row <b>200</b>, in a circle <b>180</b>; <code>1 50 50 1 1</code>: row <b>208</b>, circle <b>161</b>. -
Print the merge order for sample 1.
Answer
Store the best k for each range and recurse: <b>((20 + 20) + (10 + 20))</b>, costs 40, 30, 70 = 140. -
Print the best bracketing of a matrix chain.
Answer
Store the best k for every range and print recursively: a single matrix prints its name, a range prints ( left × right ). Dimensions 10, 30, 5, 60: <b>((A × B) × C)</b>, 4500 multiplications. -
Remove palindromes: each turn delete one palindromic substring; the fewest turns to delete everything.
Answer
dp[l][r] = fewest turns for s[l..r], empty range = 0. Either s[l] goes alone: 1 + dp[l+1][r]; or, if s[l] = s[l+1], they go together: 1 + dp[l+2][r]; or s[l] is removed together with a later equal letter s[k] (k ≥ l + 2) after the middle is cleared: dp[l+1][k−1] + dp[k+1][r]. Fill by length, O(n³). <code>abca</code> → <b>2</b> (remove b, then aca); checked against a brute force on 1500 random strings.
Quick quiz
Trays 5 5 5. What is the minimum total cost?
A) 15 · B) 20 · C) 25 · D) 30
Answer
C. Any first merge costs 10, and the last merge always lifts all 15 laddoos: 10 + 15 = 25.
Interview questions
- What makes a problem an interval DP? The answer for a range is built from answers for sub-ranges, usually by choosing a split point or the last/first operation in the range.
- Why think about the last operation? After the last operation is fixed, the two sides are independent subproblems; the first operation leaves a tangled state.
- In what order do you fill dp[l][r]? By increasing length (or l from right to left with r from left to right), so every sub-range is ready.
- What is the complexity? O(n²) states × O(n) splits = O(n³); n ≈ 400–500 is the usual limit.
- Give other interval DP problems. Matrix chain multiplication, optimal binary search trees, burst balloons, palindrome partitioning, merging stones.
- Can it be faster? For some cost functions (like this one), Knuth's optimisation gives O(n²) (episode 44).
Glossary
| Term | Meaning | Example |
|---|---|---|
| Interval DP (range DP) | DP whose state is a range [l, r] | dp[l][r] |
| Split point | Where a range is cut into two sub-ranges | k in [l, r) |
| Last merge | The final operation, joining two independent blocks | [l..k] + [k+1..r] |
| Prefix sums | pre[i] = a[0] + … + a[i−1] | sum(l..r) = pre[r+1] − pre[l] |
| Fill by length | Solve all short ranges before long ones | for len = 2..n |
| Base case | Ranges of length 1 | dp[i][i] = 0 |
| Matrix chain multiplication | Cheapest bracketing of a product of matrices | 10×30, 30×5, 5×60 → 4500 |
| Greedy | Take the locally best choice | merge the cheapest pair |
| Integer overflow | A value exceeds its type's range | -187768712704 |
| Stress test | Fast vs brute force on random small tests | all 1000 tests passed |
Summary
- The cheapest pair first fails (
150vs140); every merge order TLEs at n = 13. - Think about the last merge: two independent blocks [l..k] and [k+1..r].
- dp[l][r] = min over k of dp[l][k] + dp[k+1][r], plus sum(l..r) from prefix sums.
- Fill by length; O(n³ / 6) ≈ 10^7 for n = 400.
- Real bugs: the wrong order (
100vs190),intsums (-187768712704).
Solutions in C++, Java and Python
Problem L · Laddoo Trays
C++
#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;
vector<ll> pre(n + 1, 0); // pre[i] = a[0] + ... + a[i-1]
for (int i = 0; i < n; i++) pre[i + 1] = pre[i] + a[i];
// dp[l][r] = cheapest way to merge trays l..r into one
vector<vector<ll>> dp(n, vector<ll>(n, 0));
for (int len = 2; len <= n; len++) // short ranges first
for (int l = 0; l + len - 1 < n; l++) {
int r = l + len - 1;
dp[l][r] = LLONG_MAX;
for (int k = l; k < r; k++) // last merge: [l..k] + [k+1..r]
dp[l][r] = min(dp[l][r], dp[l][k] + dp[k + 1][r]);
dp[l][r] += pre[r + 1] - pre[l]; // the last merge lifts every laddoo
}
cout << dp[0][n - 1] << "\n";
return 0;
}
Java
import java.util.*;
import java.io.*;
public class Main {
public static void main(String[] args) throws IOException {
StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
in.nextToken(); int n = (int) in.nval;
long[] pre = new long[n + 1];
for (int i = 0; i < n; i++) { in.nextToken(); pre[i + 1] = pre[i] + (long) in.nval; }
long[][] dp = new long[n][n]; // dp[l][r]: merge trays l..r
for (int len = 2; len <= n; len++)
for (int l = 0; l + len - 1 < n; l++) {
int r = l + len - 1;
long best = Long.MAX_VALUE;
for (int k = l; k < r; k++) best = Math.min(best, dp[l][k] + dp[k + 1][r]);
dp[l][r] = best + pre[r + 1] - pre[l];
}
System.out.println(dp[0][n - 1]);
}
}
Python (fine for the samples; n = 400 means 10^7 steps, slow in pure Python)
import sys
def main():
data = sys.stdin.read().split()
n = int(data[0])
a = list(map(int, data[1:1 + n]))
pre = [0] * (n + 1)
for i, x in enumerate(a):
pre[i + 1] = pre[i] + x
dp = [[0] * n for _ in range(n)] # dp[l][r]: merge trays l..r
for length in range(2, n + 1):
for l in range(n - length + 1):
r = l + length - 1
dl = dp[l]
dp[l][r] = min(dl[k] + dp[k + 1][r] for k in range(l, r)) + pre[r + 1] - pre[l]
print(dp[0][n - 1])
main()
Next episode: DP 5: bitmask DP (a set of items, stored in one integer).