⚙️AlgorithmIntermediate

Interval DP

Key Points

•
Interval DP solves problems where the optimal answer for a segment [i, j] depends on answers of its subsegments.
•
The standard triple-loop implementation is typically O( $n^{3}$ ) time and O( $n^{2}$ ) space.
•
You process intervals by increasing length so that all needed subproblems are computed before they are used.
•
Typical transitions try all split points k between i and j and combine dp[i][k] with dp[k+1][j] plus a cost.
•
Classics include matrix chain multiplication, burst balloons, cutting a stick, and longest palindromic subsequence.
•
Some problems admit optimizations like Knuth or divide-and-conquer to reduce O( $n^{3}$ ) to O( $n^{2}$ ).
•
Careful indexing (inclusive vs. exclusive ends) and correct base cases are critical to avoid off-by-one bugs.
•
Using padding, prefix sums, and monotone opt arrays can significantly simplify and speed up implementations.

Prerequisites

→Big-O notation and asymptotic analysis — To understand why interval DP is typically O(n^3) and when optimizations reduce it to O(n^2).
→Basic dynamic programming — Familiarity with states, transitions, and base cases is necessary before tackling 2D interval DP.
→Array and string indexing — Interval DP relies on careful inclusivity/exclusivity and boundary handling.
→Prefix sums — Useful for O(1) interval weight computations in merge/cut cost problems.
→Greedy vs DP trade-offs — Recognizing when local choices fail helps motivate interval DP.
→Knuth optimization — Allows reducing O(n^3) interval DP to O(n^2) under monotonicity and quadrangle inequality.
→Divide-and-conquer optimization — Another technique that can accelerate certain interval DPs.

Detailed Explanation

Tap terms for definitions

01Overview

Interval DP is a dynamic programming technique for problems defined on contiguous segments of a sequence. The central idea is to let dp[i][j] represent the optimal value (minimum cost, maximum score, longest length, etc.) for the subarray, substring, or segment spanning indices i to j. Many natural problems decompose by choosing a split point k inside [i, j] and then combining the best answers for the left interval [i, k] and the right interval [k+1, j], possibly plus some combining cost that depends on the whole interval. Because each state depends only on strictly smaller intervals, we can compute dp in order of increasing interval length. The naive evaluation often has three nested loops: interval length, left boundary, and split point.

This pattern appears in a wide range of tasks: minimizing scalar multiplications in matrix chains, cutting a stick with minimal total cost, maximizing coins from popping balloons, determining the longest palindromic subsequence, and constructing optimal binary search trees. The time complexity is usually O(n^{3}) and the space complexity O(n^{2}), where n is the sequence length. However, when certain mathematical properties hold (e.g., quadrangle inequality and monotone opt), well-known optimizations such as Knuth optimization or divide-and-conquer optimization can reduce time to O(n^{2}).

02Intuition & Analogies

Imagine you have a chocolate bar and you want to break it into pieces. Each time you make a break, it takes effort proportional to the current bar’s length. If you plan your breaks poorly, you repeatedly pay a high cost; if you pick a smart order, you minimize the total effort. This is exactly like the “cutting a stick” problem: each break splits an interval into two smaller intervals, and the cost for that break depends on the full interval you are cutting. To decide where to break first, you must consider how that decision affects the two resulting smaller intervals—this is the essence of interval DP.

Another analogy: suppose you want to add parentheses to a long multiplication expression of matrices to reduce effort—like deciding where to put parentheses in a sentence to make it easiest to read. Parenthesizing between positions k yields two smaller sub-expressions. To pick the best overall split, you try every k, compute the cost of each sub-expression (already solved), plus the cost to combine them.

Or think of popping balloons in a line where the reward of popping one depends on its neighbors. If you pop a balloon in the middle, the line splits into two independent lines (left and right). Choosing the next balloon to pop is like choosing a sub-interval to solve next. These examples share a pattern: a big interval’s optimal answer is a function of the optimal answers of smaller intervals created by a split, with a combining cost dependent on the whole interval or the boundary elements.

Computationally, we rely on the principle of optimal substructure: after choosing a first action (a break, a parenthesis, a balloon to pop), the remaining subproblems are independent and optimally solved the same way. We organize computation by interval length so that when we need dp[i][k] and dp[k+1][j], they’re already computed.

03Formal Definition

Let a problem be defined on a sequence

a_{1}

a_{2}

\dots

a_{n}

. Define a DP table dp where dp[i][j] encodes the optimal value for the interval [i, j], 1

\leq

\leq

\leq

n. A common form of the recurrence is \[

dp[i][j] =

\operatorname{combine}\Big

(\{dp[i][k] + dp[k+1][j] +

cost

(i, j, k)\}_{k=i}^{j-1}

\Big

),\] where combine is either

min

max

depending on the objective. Base cases are usually singletons (e.g., dp[i][i] = 0 or 1) or empty intervals with a neutral element (e.g., dp[i][i-1] = 0 in half-open designs). The transition enumerates all split points k that partition [i, j] into two strictly smaller intervals, ensuring acyclicity. For some problems,

cost

(i, j, k) is independent of k (e.g., cutting a stick: cost(i, j) = length(j) - length(i)), yielding the simpler: \[

dp[i][j] =

min_{i \leq k < j}

\big

( dp[i][k] + dp[k+1][j]

\big

) + w[i][j].\] We compute dp by increasing interval length

L = j - i + 1

, ensuring all right-hand side subproblems have smaller length. The naive total time is O(

n^{3}

) because there are O(

n^{2}

) states and up to O(n) split points per state. Memory is O(

n^{2}

). Under additional structure (quadrangle inequality, monotone opt), one can restrict the search range for k, enabling O(

n^{2}

) solutions (Knuth optimization) or use divide-and-conquer optimization when costs are convex/concave in a certain sense.

04When to Use

Use interval DP when: (1) the problem asks for an optimal value on a contiguous range (subarray or substring), (2) making a single decision splits the interval into two independent sub-intervals, and (3) the total objective is the combination of the two subproblems plus (or minus) a cost related to the whole interval or the decision point. Typical scenarios include:

Parenthesization or parsing tasks: matrix chain multiplication, optimal BST construction, context-free grammar parsing variants.
Segmented cost problems: minimum total cost to cut a stick or a polygon triangulation cost.
Sequence destruction/merging: burst balloons (maximize coins), merging slimes/stones with cost equal to the sum of weights, or removing elements where reward depends on current neighbors.
Palindromic structures: longest palindromic subsequence (depends on ends) and sometimes palindrome partitioning when formulated over intervals.

You should favor interval DP over greedy or local heuristics when the combining cost creates global dependencies that invalidate local choices. Additionally, consider it when recursion naturally branches on a split position and subproblems are disjoint intervals. If the naive O(n^{3}) is too slow, check whether the cost function satisfies conditions for Knuth or divide-and-conquer optimization, or if a different state design (e.g., half-open intervals or padded boundaries) simplifies transitions.

⚠️Common Mistakes

Off-by-one errors: Mixing inclusive [i, j] with half-open [i, j) designs causes incorrect base cases and transitions. Decide your convention up front and stick to it. For inclusive intervals, base cases often set dp[i][i] and iterate lengths from 2 to n.
Wrong iteration order: If you don’t iterate by increasing length, you may use uninitialized subproblems. Always ensure sub-intervals are computed before super-intervals.
Incorrect cost indexing: In problems like matrix chain multiplication or cutting sticks, costs depend on boundary indices (e.g., dims[i]·dims[k+1]·dims[j+1] or pos[j]−pos[i]). Misaligned arrays (missing padding or boundary elements) lead to wrong answers. Use padding (e.g., add 1 at both ends for Burst Balloons; add 0 and L for cut positions) and compute prefix sums if needed.
Not initializing with +∞/−∞: When minimizing/maximizing, initialize dp[i][j] with a sentinel (e.g., INF for min, 0 or −INF for max). Forgetting this leaves stale values that block improvements.
Forgetting empty-interval states: Some recurrences are cleaner with empty intervals dp[i][i−1] = 0 or half-open dp[l][r] where l+1 = r is the smallest. Omitting these leads to extra if-branches.
Assuming optimizations always apply: Knuth optimization requires specific monotonicity conditions (opt[i][j−1] \le opt[i][j] \le opt[i+1][j]) plus quadrangle inequality. Using it without verifying may silently break correctness.
Memory blow-ups: dp is O(n^{2}); for large n, consider rolling arrays, compressing states, or verifying whether an O(n^{2}) time and memory solution fits limits.

Key Formulas

General Interval DP Recurrence

dp [i] [j] = i \leq k < j min (dp [i] [k] + dp [k + 1] [j] + cost (i, j, k))

Explanation: The optimal value on [i, j] comes from choosing a split k, combining optimal sub-interval values, plus a cost that may depend on i, j, and k. Use min or max depending on the objective.

Split with Interval-Only Cost

dp [i] [j] = i \leq k < j min (dp [i] [k] + dp [k + 1] [j]) + w [i] [j]

Explanation: When the combination cost depends only on the entire interval [i, j] and not on k, the transition simplifies, a setting where Knuth optimization may apply.

Number of Intervals

states = ℓ = 1 \sum n (n - ℓ + 1) = \frac{n ( n + 1 )}{2}

Explanation: There are O( $n^{2}$ ) distinct intervals of a sequence of length n. This is why interval DP tables are typically O( $n^{2}$ ) in size.

Naive Time Complexity

T (n) = Θ (n^{2} \cdot n) = Θ (n^{3})

Explanation: Computing O( $n^{2}$ ) states and trying O(n) splits per state yields cubic time. This is the default complexity for unoptimized interval DP.

Knuth Monotonicity

opt [i] [j - 1] \leq opt [i] [j] \leq opt [i + 1] [j]

Explanation: If the optimal split index is monotone, you can restrict the k-search to a narrow band, reducing the transition from O(n) to amortized O(1) per state and overall O( $n^{2}$ ).

Longest Palindromic Subsequence Recurrence

LPS (i, j) = ⎩ ⎨ ⎧ 1, LPS (i + 1, j - 1) + 2, max {LPS (i + 1, j), LPS (i, j - 1)}, i = j, a_{i} = a_{j}, a_{i} \neq = a_{j} .

Explanation: If the end characters match, extend a smaller palindrome; otherwise, drop one end. This is an O( $n^{2}$ ) interval DP without split enumeration.

Matrix Chain Multiplication

MCM (i, j) = i \leq k < j min (MCM (i, k) + MCM (k + 1, j) + d_{i} d_{k + 1} d_{j + 1})

Explanation: Cost to multiply matrices i..j depends on the split k and the boundary dimensions. This is a canonical O( $n^{3}$ ) interval DP.

Complexity Analysis

Let n be the length of the sequence. An interval DP maintains a 2D table dp of size O(

n^{2}

), since there are

\frac{n ( n + 1 )}{2}

intervals. The standard computation iterates over interval lengths L from 1 to n, and for each left boundary i computes

j = i + L

− 1. For each state (i, j), a naive transition often tries all split points k in [i, j), which yields O(n) work per state. Therefore, the total running time sums to O(

n^{2}

· n) = O(

n^{3}

). Memory usage is O(

n^{2}

), storing dp plus, optionally, an auxiliary table to reconstruct choices (e.g., a split index per state), which can double the constant factor but remains O(

n^{2}

). Some interval DPs avoid the split loop entirely by depending only on neighboring states (e.g., longest palindromic subsequence), achieving O(

n^{2}

) time. Others admit structure enabling optimizations. With Knuth optimization, if the cost function w[i][j] and the DP form satisfy quadrangle inequality and monotone-opt properties, the argmin opt[i][j] lies between opt[i][j−1] and opt[i+1][j]. Restricting k to this small range reduces the amortized cost per state to O(1), giving overall O(

n^{2}

) time while keeping O(

n^{2}

) space. Divide-and-conquer optimization can also reduce transitions from O(n) to O(log n) (or O(1)) in suitable convex settings, leading to O(

n^{2}

log n) or O(

n^{2}

). Practical performance depends on constants: tight loops over the split k are cache-friendly, and using half-open intervals or padding can simplify boundary checks. If n is large (e.g., > 2000) and the naive O(

n^{3}

) is too slow, first check if the problem admits Knuth or DnC optimizations; otherwise consider problem-specific heuristics, pruning, or alternative formulations.

Code Examples

Matrix Chain Multiplication (min multiplications) with reconstruction

1 #include <bits/stdc++.h>
2 using namespace std;
3 
4 // Matrix Chain Multiplication using Interval DP
5 // Given dimensions d[0..n], where matrix i has size d[i-1] x d[i],
6 // find the minimum number of scalar multiplications to multiply the chain.
7 // Also reconstruct an optimal parenthesization.
8 
9 static const long long INF = (1LL<<62);
10 
11 string build_parenthesis(const vector<vector<int>>& split, int i, int j) {
12     if (i == j) {
13         return "A" + to_string(i + 1); // matrices labeled A1..An
14     }
15     int k = split[i][j];
16     return "(" + build_parenthesis(split, i, k) + " x " + build_parenthesis(split, k + 1, j) + ")";
17 }
18 
19 int main() {
20     ios::sync_with_stdio(false);
21     cin.tie(nullptr);
22 
23     // Example: 4 matrices with dimensions 10x30, 30x5, 5x60, 60x10
24     // Input format:
25     // n
26     // d0 d1 d2 ... dn
27     // Sample: n=4, d: 10 30 5 60 10
28     int n;
29     if (!(cin >> n)) {
30         // Fallback demo if no input is provided
31         n = 4;
32         vector<long long> demo = {10, 30, 5, 60, 10};
33         vector<long long> d = demo;
34         vector<vector<long long>> dp(n, vector<long long>(n, 0));
35         vector<vector<int>> split(n, vector<int>(n, -1));
36         for (int len = 2; len <= n; ++len) {
37             for (int i = 0; i + len - 1 < n; ++i) {
38                 int j = i + len - 1;
39                 dp[i][j] = INF;
40                 for (int k = i; k < j; ++k) {
41                     long long cost = dp[i][k] + dp[k+1][j] + d[i]*d[k+1]*d[j+1];
42                     if (cost < dp[i][j]) {
43                         dp[i][j] = cost;
44                         split[i][j] = k;
45                     }
46                 }
47             }
48         }
49         cout << dp[0][n-1] << "\n";
50         cout << build_parenthesis(split, 0, n-1) << "\n";
51         return 0;
52     }
53 
54     vector<long long> d(n+1);
55     for (int i = 0; i <= n; ++i) cin >> d[i];
56 
57     vector<vector<long long>> dp(n, vector<long long>(n, 0));
58     vector<vector<int>> split(n, vector<int>(n, -1));
59 
60     // dp[i][i] = 0 by initialization (one matrix, no multiplication)
61     for (int len = 2; len <= n; ++len) {               // interval length
62         for (int i = 0; i + len - 1 < n; ++i) {        // left index
63             int j = i + len - 1;                       // right index
64             dp[i][j] = INF;
65             for (int k = i; k < j; ++k) {              // split point
66                 long long cost = dp[i][k] + dp[k+1][j] + d[i]*d[k+1]*d[j+1];
67                 if (cost < dp[i][j]) {
68                     dp[i][j] = cost;
69                     split[i][j] = k;
70                 }
71             }
72         }
73     }
74 
75     cout << dp[0][n-1] << "\n";
76     cout << build_parenthesis(split, 0, n-1) << "\n";
77     return 0;
78 }
79

We compute dp[i][j] as the minimum scalar multiplications needed to multiply matrices i..j. The transition tries all last split positions k and adds the boundary multiplication cost d[i]·d[k+1]·d[j+1]. The split table stores optimal k for reconstruction, allowing us to print an optimal parenthesization.

Time: O(n^3)Space: O(n^2)

Burst Balloons (maximize coins) using open-interval DP

1 #include <bits/stdc++.h>
2 using namespace std;
3 
4 // Burst Balloons (LeetCode 312) via Interval DP.
5 // We pad the array with 1 at both ends and use open intervals (l, r).
6 // dp[l][r] = max coins obtainable by bursting balloons strictly between l and r.
7 
8 int main() {
9     ios::sync_with_stdio(false);
10     cin.tie(nullptr);
11 
12     // Input: n, followed by n balloon values
13     // Example: 4\n3 1 5 8
14     int n; 
15     if (!(cin >> n)) {
16         n = 4; vector<int> a = {3,1,5,8};
17         vector<int> nums(n + 2, 1);
18         for (int i = 0; i < n; ++i) nums[i+1] = a[i];
19         int m = n + 2;
20         vector<vector<int>> dp(m, vector<int>(m, 0));
21         for (int len = 2; len < m; ++len) {             // length of open interval
22             for (int l = 0; l + len < m; ++l) {
23                 int r = l + len;
24                 // try popping k last in (l, r)
25                 for (int k = l + 1; k < r; ++k) {
26                     dp[l][r] = max(dp[l][r], dp[l][k] + dp[k][r] + nums[l]*nums[k]*nums[r]);
27                 }
28             }
29         }
30         cout << dp[0][m-1] << "\n"; // maximum coins
31         return 0;
32     }
33 
34     vector<int> a(n);
35     for (int i = 0; i < n; ++i) cin >> a[i];
36 
37     vector<int> nums(n + 2, 1);
38     for (int i = 0; i < n; ++i) nums[i+1] = a[i];
39     int m = n + 2;
40     vector<vector<int>> dp(m, vector<int>(m, 0));
41 
42     for (int len = 2; len < m; ++len) {
43         for (int l = 0; l + len < m; ++l) {
44             int r = l + len;
45             for (int k = l + 1; k < r; ++k) {
46                 dp[l][r] = max(dp[l][r], dp[l][k] + dp[k][r] + nums[l]*nums[k]*nums[r]);
47             }
48         }
49     }
50 
51     cout << dp[0][m-1] << "\n";
52     return 0;
53 }
54

We pad with 1 on both ends to handle boundary multipliers uniformly. dp[l][r] stores the best coins in the open interval (l, r). Choosing k as the last balloon popped splits (l, r) into independent subproblems (l, k) and (k, r), and yields nums[l]*nums[k]*nums[r] coins for popping k last.

Time: O(n^3)Space: O(n^2)

Cutting a Stick with Knuth Optimization (O(n^2))

1 #include <bits/stdc++.h>
2 using namespace std;
3 
4 // Minimum cost to cut a stick. Cuts are at positions c[1..m] on a stick of length L.
5 // Each cut costs the current segment length. We seek the minimum total cost.
6 // Interval DP form: dp[i][j] = min_{i<k<j} dp[i][k] + dp[k][j] + (pos[j]-pos[i])
7 // where pos[0]=0, pos[m+1]=L, and i,j index the augmented cut positions.
8 // This DP admits Knuth optimization: opt[i][j-1] <= opt[i][j] <= opt[i+1][j].
9 
10 static const int INF = 1e9;
11 
12 int main() {
13     ios::sync_with_stdio(false);
14     cin.tie(nullptr);
15 
16     // Input: L m \n c1 c2 ... cm
17     // Example: 10 3 \n 2 4 7
18     int L, m;
19     if (!(cin >> L >> m)) {
20         L = 10; m = 3; vector<int> cuts = {2,4,7};
21         vector<int> pos(m + 2);
22         pos[0] = 0; pos[m+1] = L;
23         for (int i = 1; i <= m; ++i) pos[i] = cuts[i-1];
24         sort(pos.begin(), pos.end());
25         int M = m + 2;
26         vector<vector<int>> dp(M, vector<int>(M, 0));
27         vector<vector<int>> opt(M, vector<int>(M, 0));
28         for (int i = 0; i + 1 < M; ++i) opt[i][i+1] = i; // no cut inside
29 
30         for (int len = 2; len < M; ++len) {
31             for (int i = 0; i + len < M; ++i) {
32                 int j = i + len;
33                 dp[i][j] = INF;
34                 int start = opt[i][j-1];
35                 int finish = opt[i+1][j];
36                 if (start > finish) swap(start, finish); // be safe
37                 for (int k = start; k <= finish; ++k) {
38                     int cost = dp[i][k] + dp[k][j] + (pos[j] - pos[i]);
39                     if (cost < dp[i][j]) {
40                         dp[i][j] = cost;
41                         opt[i][j] = k;
42                     }
43                 }
44             }
45         }
46         cout << dp[0][M-1] << "\n";
47         return 0;
48     }
49 
50     vector<int> cuts(m);
51     for (int i = 0; i < m; ++i) cin >> cuts[i];
52     vector<int> pos(m + 2);
53     pos[0] = 0; pos[m+1] = L;
54     for (int i = 1; i <= m; ++i) pos[i] = cuts[i-1];
55     sort(pos.begin(), pos.end());
56 
57     int M = m + 2;
58     vector<vector<int>> dp(M, vector<int>(M, 0));
59     vector<vector<int>> opt(M, vector<int>(M, 0));
60     for (int i = 0; i + 1 < M; ++i) opt[i][i+1] = i; // base: no cut inside
61 
62     // Knuth-optimized DP: k-search confined to [opt[i][j-1], opt[i+1][j]]
63     for (int len = 2; len < M; ++len) {
64         for (int i = 0; i + len < M; ++i) {
65             int j = i + len;
66             dp[i][j] = INF;
67             int start = opt[i][j-1];
68             int finish = opt[i+1][j];
69             if (start > finish) swap(start, finish);
70             for (int k = start; k <= finish; ++k) {
71                 int cost = dp[i][k] + dp[k][j] + (pos[j] - pos[i]);
72                 if (cost < dp[i][j]) {
73                     dp[i][j] = cost;
74                     opt[i][j] = k;
75                 }
76             }
77         }
78     }
79 
80     cout << dp[0][M-1] << "\n";
81     return 0;
82 }
83

We augment cut positions with 0 and L. The DP state dp[i][j] is the minimum cost to fully cut segment (pos[i], pos[j]). The combining cost is the segment length pos[j]−pos[i], independent of k, so this problem satisfies Knuth’s conditions. We maintain opt[i][j] (the best k) and restrict the k-loop to [opt[i][j−1], opt[i+1][j]], reducing time from O(m^3) to O(m^2).

Time: O(m^2)Space: O(m^2)

Longest Palindromic Subsequence (O(n^2) interval DP)

1 #include <bits/stdc++.h>
2 using namespace std;
3 
4 // Longest Palindromic Subsequence via Interval DP.
5 // dp[i][j] = length of the LPS in s[i..j].
6 
7 int main() {
8     ios::sync_with_stdio(false);
9     cin.tie(nullptr);
10 
11     string s;
12     if (!(cin >> s)) {
13         s = "bbbab";
14     }
15     int n = (int)s.size();
16     vector<vector<int>> dp(n, vector<int>(n, 0));
17 
18     // Base: single character is a palindrome of length 1
19     for (int i = 0; i < n; ++i) dp[i][i] = 1;
20 
21     // Process by increasing interval length
22     for (int len = 2; len <= n; ++len) {
23         for (int i = 0; i + len - 1 < n; ++i) {
24             int j = i + len - 1;
25             if (s[i] == s[j]) {
26                 dp[i][j] = (len == 2) ? 2 : dp[i+1][j-1] + 2;
27             } else {
28                 dp[i][j] = max(dp[i+1][j], dp[i][j-1]);
29             }
30         }
31     }
32 
33     cout << dp[0][n-1] << "\n";
34     return 0;
35 }
36

We fill dp by increasing substring length. If the ends match, we extend the best inside subsequence by 2; if not, we drop one end and take the better. No split enumeration is required, so the solution is O(n^2) time and O(n^2) space.

Time: O(n^2)Space: O(n^2)

1	#include <bits/stdc++.h>
2	using namespace std;
3
4	// Matrix Chain Multiplication using Interval DP
5	// Given dimensions d[0..n], where matrix i has size d[i-1] x d[i],
6	// find the minimum number of scalar multiplications to multiply the chain.
7	// Also reconstruct an optimal parenthesization.
8
9	static const long long INF = (1LL<<62);
10
11	string build_parenthesis(const vector<vector<int>>& split, int i, int j) {
12	if (i == j) {
13	return "A" + to_string(i + 1); // matrices labeled A1..An
14	}
15	int k = split[i][j];
16	return "(" + build_parenthesis(split, i, k) + " x " + build_parenthesis(split, k + 1, j) + ")";
17	}
18
19	int main() {
20	ios::sync_with_stdio(false);
21	cin.tie(nullptr);
22
23	// Example: 4 matrices with dimensions 10x30, 30x5, 5x60, 60x10
24	// Input format:
25	// n
26	// d0 d1 d2 ... dn
27	// Sample: n=4, d: 10 30 5 60 10
28	int n;
29	if (!(cin >> n)) {
30	// Fallback demo if no input is provided
31	n = 4;
32	vector<long long> demo = {10, 30, 5, 60, 10};
33	vector<long long> d = demo;
34	vector<vector<long long>> dp(n, vector<long long>(n, 0));
35	vector<vector<int>> split(n, vector<int>(n, -1));
36	for (int len = 2; len <= n; ++len) {
37	for (int i = 0; i + len - 1 < n; ++i) {
38	int j = i + len - 1;
39	dp[i][j] = INF;
40	for (int k = i; k < j; ++k) {
41	long long cost = dp[i][k] + dp[k+1][j] + d[i]d[k+1]d[j+1];
42	if (cost < dp[i][j]) {
43	dp[i][j] = cost;
44	split[i][j] = k;
45	}
46	}
47	}
48	}
49	cout << dp[0][n-1] << "\n";
50	cout << build_parenthesis(split, 0, n-1) << "\n";
51	return 0;
52	}
53
54	vector<long long> d(n+1);
55	for (int i = 0; i <= n; ++i) cin >> d[i];
56
57	vector<vector<long long>> dp(n, vector<long long>(n, 0));
58	vector<vector<int>> split(n, vector<int>(n, -1));
59
60	// dp[i][i] = 0 by initialization (one matrix, no multiplication)
61	for (int len = 2; len <= n; ++len) { // interval length
62	for (int i = 0; i + len - 1 < n; ++i) { // left index
63	int j = i + len - 1; // right index
64	dp[i][j] = INF;
65	for (int k = i; k < j; ++k) { // split point
66	long long cost = dp[i][k] + dp[k+1][j] + d[i]d[k+1]d[j+1];
67	if (cost < dp[i][j]) {
68	dp[i][j] = cost;
69	split[i][j] = k;
70	}
71	}
72	}
73	}
74
75	cout << dp[0][n-1] << "\n";
76	cout << build_parenthesis(split, 0, n-1) << "\n";
77	return 0;
78	}
79

1	#include <bits/stdc++.h>
2	using namespace std;
3
4	// Burst Balloons (LeetCode 312) via Interval DP.
5	// We pad the array with 1 at both ends and use open intervals (l, r).
6	// dp[l][r] = max coins obtainable by bursting balloons strictly between l and r.
7
8	int main() {
9	ios::sync_with_stdio(false);
10	cin.tie(nullptr);
11
12	// Input: n, followed by n balloon values
13	// Example: 4\n3 1 5 8
14	int n;
15	if (!(cin >> n)) {
16	n = 4; vector<int> a = {3,1,5,8};
17	vector<int> nums(n + 2, 1);
18	for (int i = 0; i < n; ++i) nums[i+1] = a[i];
19	int m = n + 2;
20	vector<vector<int>> dp(m, vector<int>(m, 0));
21	for (int len = 2; len < m; ++len) { // length of open interval
22	for (int l = 0; l + len < m; ++l) {
23	int r = l + len;
24	// try popping k last in (l, r)
25	for (int k = l + 1; k < r; ++k) {
26	dp[l][r] = max(dp[l][r], dp[l][k] + dp[k][r] + nums[l]nums[k]nums[r]);
27	}
28	}
29	}
30	cout << dp[0][m-1] << "\n"; // maximum coins
31	return 0;
32	}
33
34	vector<int> a(n);
35	for (int i = 0; i < n; ++i) cin >> a[i];
36
37	vector<int> nums(n + 2, 1);
38	for (int i = 0; i < n; ++i) nums[i+1] = a[i];
39	int m = n + 2;
40	vector<vector<int>> dp(m, vector<int>(m, 0));
41
42	for (int len = 2; len < m; ++len) {
43	for (int l = 0; l + len < m; ++l) {
44	int r = l + len;
45	for (int k = l + 1; k < r; ++k) {
46	dp[l][r] = max(dp[l][r], dp[l][k] + dp[k][r] + nums[l]nums[k]nums[r]);
47	}
48	}
49	}
50
51	cout << dp[0][m-1] << "\n";
52	return 0;
53	}
54

1	#include <bits/stdc++.h>
2	using namespace std;
3
4	// Minimum cost to cut a stick. Cuts are at positions c[1..m] on a stick of length L.
5	// Each cut costs the current segment length. We seek the minimum total cost.
6	// Interval DP form: dp[i][j] = min_{i<k<j} dp[i][k] + dp[k][j] + (pos[j]-pos[i])
7	// where pos[0]=0, pos[m+1]=L, and i,j index the augmented cut positions.
8	// This DP admits Knuth optimization: opt[i][j-1] <= opt[i][j] <= opt[i+1][j].
9
10	static const int INF = 1e9;
11
12	int main() {
13	ios::sync_with_stdio(false);
14	cin.tie(nullptr);
15
16	// Input: L m \n c1 c2 ... cm
17	// Example: 10 3 \n 2 4 7
18	int L, m;
19	if (!(cin >> L >> m)) {
20	L = 10; m = 3; vector<int> cuts = {2,4,7};
21	vector<int> pos(m + 2);
22	pos[0] = 0; pos[m+1] = L;
23	for (int i = 1; i <= m; ++i) pos[i] = cuts[i-1];
24	sort(pos.begin(), pos.end());
25	int M = m + 2;
26	vector<vector<int>> dp(M, vector<int>(M, 0));
27	vector<vector<int>> opt(M, vector<int>(M, 0));
28	for (int i = 0; i + 1 < M; ++i) opt[i][i+1] = i; // no cut inside
29
30	for (int len = 2; len < M; ++len) {
31	for (int i = 0; i + len < M; ++i) {
32	int j = i + len;
33	dp[i][j] = INF;
34	int start = opt[i][j-1];
35	int finish = opt[i+1][j];
36	if (start > finish) swap(start, finish); // be safe
37	for (int k = start; k <= finish; ++k) {
38	int cost = dp[i][k] + dp[k][j] + (pos[j] - pos[i]);
39	if (cost < dp[i][j]) {
40	dp[i][j] = cost;
41	opt[i][j] = k;
42	}
43	}
44	}
45	}
46	cout << dp[0][M-1] << "\n";
47	return 0;
48	}
49
50	vector<int> cuts(m);
51	for (int i = 0; i < m; ++i) cin >> cuts[i];
52	vector<int> pos(m + 2);
53	pos[0] = 0; pos[m+1] = L;
54	for (int i = 1; i <= m; ++i) pos[i] = cuts[i-1];
55	sort(pos.begin(), pos.end());
56
57	int M = m + 2;
58	vector<vector<int>> dp(M, vector<int>(M, 0));
59	vector<vector<int>> opt(M, vector<int>(M, 0));
60	for (int i = 0; i + 1 < M; ++i) opt[i][i+1] = i; // base: no cut inside
61
62	// Knuth-optimized DP: k-search confined to [opt[i][j-1], opt[i+1][j]]
63	for (int len = 2; len < M; ++len) {
64	for (int i = 0; i + len < M; ++i) {
65	int j = i + len;
66	dp[i][j] = INF;
67	int start = opt[i][j-1];
68	int finish = opt[i+1][j];
69	if (start > finish) swap(start, finish);
70	for (int k = start; k <= finish; ++k) {
71	int cost = dp[i][k] + dp[k][j] + (pos[j] - pos[i]);
72	if (cost < dp[i][j]) {
73	dp[i][j] = cost;
74	opt[i][j] = k;
75	}
76	}
77	}
78	}
79
80	cout << dp[0][M-1] << "\n";
81	return 0;
82	}
83

1	#include <bits/stdc++.h>
2	using namespace std;
3
4	// Longest Palindromic Subsequence via Interval DP.
5	// dp[i][j] = length of the LPS in s[i..j].
6
7	int main() {
8	ios::sync_with_stdio(false);
9	cin.tie(nullptr);
10
11	string s;
12	if (!(cin >> s)) {
13	s = "bbbab";
14	}
15	int n = (int)s.size();
16	vector<vector<int>> dp(n, vector<int>(n, 0));
17
18	// Base: single character is a palindrome of length 1
19	for (int i = 0; i < n; ++i) dp[i][i] = 1;
20
21	// Process by increasing interval length
22	for (int len = 2; len <= n; ++len) {
23	for (int i = 0; i + len - 1 < n; ++i) {
24	int j = i + len - 1;
25	if (s[i] == s[j]) {
26	dp[i][j] = (len == 2) ? 2 : dp[i+1][j-1] + 2;
27	} else {
28	dp[i][j] = max(dp[i+1][j], dp[i][j-1]);
29	}
30	}
31	}
32
33	cout << dp[0][n-1] << "\n";
34	return 0;
35	}
36