State: dp[i][j] = answer for the interval [i, j]Key Insight: Solve for small intervals first, then larger ones. Often involves choosing a split point k.The Template:
Copy
for len = 1 to n: // Interval length for i = 0 to n-len: // Left endpoint j = i + len - 1 // Right endpoint for k = i to j: // Split point dp[i][j] = optimize(dp[i][k], dp[k+1][j], cost)
Why this order? When computing dp[i][j], we need dp[i][k] and dp[k+1][j]—both are shorter intervals. By iterating by length, we ensure dependencies are already computed.Visual Example (n=4, computing dp[0][3]):
Copy
Length 1: dp[0][0], dp[1][1], dp[2][2], dp[3][3] (base cases)Length 2: dp[0][1], dp[1][2], dp[2][3]Length 3: dp[0][2], dp[1][3]Length 4: dp[0][3] ← needs dp[0][k] and dp[k+1][3] for k=0,1,2 All those are already computed ✓
State: dp[i][j] = minimum cost to multiply matrices i through j
Transition: Try all split points k; cost = dp[i][k] + dp[k+1][j] + dims[i] × dims[k+1] × dims[j+1]
Copy
int matrixChainMultiplication(vector<int>& dims) { int n = dims.size() - 1; // n matrices vector<vector<int>> dp(n, vector<int>(n, 0)); // len = length of chain for (int len = 2; len <= n; len++) { for (int i = 0; i <= n - len; i++) { int j = i + len - 1; dp[i][j] = INT_MAX; // Try all split points for (int k = i; k < j; k++) { int cost = dp[i][k] + dp[k + 1][j] + dims[i] * dims[k + 1] * dims[j + 1]; dp[i][j] = min(dp[i][j], cost); } } } return dp[0][n - 1];}
Problem: Burst balloons to maximize coins. Bursting balloon i gives nums[left] * nums[i] * nums[right] coins.Key Insight: Think backwards—which balloon do we burst last in a range?
Copy
int maxCoins(vector<int>& nums) { int n = nums.size(); // Add 1s at boundaries vector<int> arr(n + 2); arr[0] = arr[n + 1] = 1; for (int i = 0; i < n; i++) arr[i + 1] = nums[i]; n += 2; vector<vector<int>> dp(n, vector<int>(n, 0)); for (int len = 2; len < n; len++) { for (int left = 0; left < n - len; left++) { int right = left + len; for (int k = left + 1; k < right; k++) { // k is the LAST balloon burst in (left, right) dp[left][right] = max(dp[left][right], dp[left][k] + dp[k][right] + arr[left] * arr[k] * arr[right]); } } } return dp[0][n - 1];}
Problem: Visit all cities exactly once and return to start with minimum cost.
Copy
int tsp(vector<vector<int>>& dist) { int n = dist.size(); int INF = 1e9; // dp[mask][i] = min cost to reach city i, having visited cities in mask vector<vector<int>> dp(1 << n, vector<int>(n, INF)); dp[1][0] = 0; // Start at city 0 for (int mask = 1; mask < (1 << n); mask++) { for (int u = 0; u < n; u++) { if (!(mask & (1 << u))) continue; // u not in mask if (dp[mask][u] == INF) continue; for (int v = 0; v < n; v++) { if (mask & (1 << v)) continue; // v already visited int newMask = mask | (1 << v); dp[newMask][v] = min(dp[newMask][v], dp[mask][u] + dist[u][v]); } } } // Return to city 0 int allVisited = (1 << n) - 1; int ans = INF; for (int i = 0; i < n; i++) { ans = min(ans, dp[allVisited][i] + dist[i][0]); } return ans;}
Problem: Partition n elements into groups, each group following rules.
Copy
// Example: Count ways to partition n people into teams of size kint countPartitions(int n, int k) { // dp[mask] = ways to partition people in mask into teams vector<long long> dp(1 << n, 0); dp[0] = 1; // Precompute valid teams (subsets of size k) vector<int> validTeams; for (int mask = 0; mask < (1 << n); mask++) { if (__builtin_popcount(mask) == k) { validTeams.push_back(mask); } } for (int mask = 0; mask < (1 << n); mask++) { if (dp[mask] == 0) continue; // Find first unassigned person (to avoid counting same partition twice) int first = -1; for (int i = 0; i < n; i++) { if (!(mask & (1 << i))) { first = i; break; } } if (first == -1) continue; for (int team : validTeams) { // Team must include 'first' and not overlap with mask if (!(team & (1 << first))) continue; if (team & mask) continue; dp[mask | team] += dp[mask]; } } return dp[(1 << n) - 1];}
// Iterate over all subsets of maskfor (int sub = mask; sub > 0; sub = (sub - 1) & mask) { // sub is a subset of mask}// Count set bitsint count = __builtin_popcount(mask);// Check if bit i is setbool isSet = (mask >> i) & 1;// Set bit imask |= (1 << i);// Clear bit i mask &= ~(1 << i);// Toggle bit imask ^= (1 << i);// Get lowest set bitint lowest = mask & (-mask);// Clear lowest set bitmask &= (mask - 1);
When dp[i] = min/max(dp[j] + cost(j, i)) for j in sliding window.
Copy
// Example: Jump Game with max k jumps, minimize sum of heightsint minCost(vector<int>& heights, int k) { int n = heights.size(); vector<int> dp(n, INT_MAX); dp[0] = 0; deque<int> dq; // Monotonic deque of indices dq.push_back(0); for (int i = 1; i < n; i++) { // Remove out-of-range elements while (!dq.empty() && dq.front() < i - k) { dq.pop_front(); } dp[i] = dp[dq.front()] + abs(heights[i] - heights[dq.front()]); // Maintain monotonicity while (!dq.empty() && dp[dq.back()] >= dp[i]) { dq.pop_back(); } dq.push_back(i); } return dp[n - 1];}