Linear dynamic programming problems, such as knapsack variations, typically process states in a strict sequential order—either forward or backward. Each state depends strictly on previously computed states. Interval dynamic programming breaks this sequential dependency. In many scenarios, the order of combining or splitting elements is not fixed, and choosing a later element does not mandate choosing an earlier one first.

The core strategy of interval DP involves scaling up from smaller segments to larger ones. The problem phase is usually defined by the interval length. The standard implementation pattern iterates over the segment length, then the left boundary, derives the right boundary, and finally evaluates split points to transition states.

Interval DP problems generally fall into two categories:

• Merging: Combining two or more adjacent sub-segments into a single entity. The optimal solution for a larger segment is derived by evaluating all possible split points and combining the optimal solutions of the left and right sub-segments.
• Splitting: Decomposing a segment into independent parts. Similar to merging, it requires finding the optimal partition point, but ofteen necessitates handling constraints like the number of splits or specific delimiter placement.

Minimum Cost of Sequential Merging

Given a sequence of N elements, each with a specific weight, the task is to combine them into one single group. Only two adjacent groups can be merged at a time. The cost of a merge operation equals the sum of the weights of the two groups being merged. The goal is to minimize the total cost of merging all elements into one.

A greedy approach fails here because early merging decisions alter the weights of adjacent groups, affecting subsequent costs. The problem requires a DP approach.

Let dp[l][r] represent the minimum cost to merge the segment from index l to r. The final operation to form [l, r] must be merging a left part [l, m] and a right part [m+1, r]. The cost of this final operation is the sum of all elements in [l, r], regardless of how they were previously merged. By iterating over all possible split points m, the transition is:

dp[l][r] = min(dp[l][m] + dp[m+1][r] + sum(l, r))

To efficiently compute sum(l, r), a prefix sum array is utilized. The iteration starts from length 1 (where dp[i][i] = 0 since no merge is needed) and scales up to length N.

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    int n;
    cin >> n;
    vector<int> val(n + 1);
    vector<long long> prefix(n + 1, 0);
    for (int i = 1; i <= n; ++i) {
        cin >> val[i];
        prefix[i] = prefix[i - 1] + val[i];
    }
    
    vector<vector<long long>> dp(n + 1, vector<long long>(n + 1, 1e18));
    for (int i = 1; i <= n; ++i) dp[i][i] = 0;
    
    for (int len = 2; len <= n; ++len) {
        for (int left = 1; left + len - 1 <= n; ++left) {
            int right = left + len - 1;
            for (int mid = left; mid < right; ++mid) {
                long long cost = dp[left][mid] + dp[mid + 1][right] + prefix[right] - prefix[left - 1];
                dp[left][right] = min(dp[left][right], cost);
            }
        }
    }
    cout << dp[1][n] << endl;
    return 0;
}

Maximizing Product with Multiplication Signs

Given a numeric string of length N and K multiplication signs, insert the signs into the string to form K+1 integers. The objective is to maximize the product of these integers.

While this is a splitting problem, tracking the exact distribution of signs between left and right sub-segments would require a 3D state array, drastically increasing time and space complexity. Instead, we impose a implicit ordering on the signs. By considering the last placed sign, the problem simplifies. If the last sign is placed after the m-th digit, the first m digits must contain exactly K-1 signs, and the remaining digits form a single integer.

Let dp[i][j] denote the maximum product achievable using the first i digits with j multiplication signs. The transition becomes:

dp[i][j] = max(dp[m][j-1] * segment_val(m+1, i)) for all m from j to i-1.

Here, segment_val(l, r) represents the integer value of the substring from l to r. The base case is dp[i][0] = segment_val(1, i).

#include <iostream>
#include <vector>
#include <string>

using namespace std;

int main() {
    int n, k;
    string seq;
    cin >> n >> k >> seq;
    
    // Precompute integer value of substring [l, r] (1-indexed)
    vector<vector<long long>> segment_val(n + 1, vector<long long>(n + 1, 0));
    for (int l = 1; l <= n; ++l) {
        segment_val[l][l] = seq[l - 1] - '0';
        for (int r = l + 1; r <= n; ++r) {
            segment_val[l][r] = segment_val[l][r - 1] * 10 + (seq[r - 1] - '0');
        }
    }
    
    // dp[i][j] = max product for first i digits with j signs
    vector<vector<long long>> dp(n + 1, vector<long long>(k + 1, 0));
    for (int i = 1; i <= n; ++i) dp[i][0] = segment_val[1][i];
    
    for (int i = 2; i <= n; ++i) {
        for (int j = 1; j <= min(i - 1, k); ++j) {
            for (int m = j; m < i; ++m) { // Last sign placed after m-th digit
                dp[i][j] = max(dp[i][j], dp[m][j - 1] * segment_val[m + 1][i]);
            }
        }
    }
    
    cout << dp[n][k] << endl;
    return 0;
}

Minimum Insertions for Palindrome

Given an arbitrary string, determine the minimum number of characters required to insert in to it so that it becomes a palindrome.

Let dp[i][j] be the minimum insertions needed to transform the substring from index i to j into a palindrome. For any substring, if the outer characters s[i] and s[j] match, no insertion is needed for them, and the result depends entirely on the inner substring dp[i+1][j-1]. If they do not match, we must insert a character either at the beginning to match s[j] or at the end to match s[i]. This leads to two possibilities: solving dp[i+1][j] or solving dp[i][j-1], each adding one insertion operation.

The transition logic is:

• If s[i] == s[j]: dp[i][j] = dp[i+1][j-1]
• If s[i] != s[j]: dp[i][j] = min(dp[i+1][j], dp[i][j-1]) + 1

The base cases are all substrings of length 1, which are already palindromes and require 0 insertions. The computation proceeds by increasing substring length.

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>

using namespace std;

int main() {
    string text;
    cin >> text;
    int size = text.length();
    
    vector<vector<int>> memo(size, vector<int>(size, 0));
    
    for (int len = 2; len <= size; ++len) {
        for (int i = 0; i + len - 1 < size; ++i) {
            int j = i + len - 1;
            if (text[i] == text[j]) {
                memo[i][j] = memo[i + 1][j - 1];
            } else {
                memo[i][j] = min(memo[i + 1][j], memo[i][j - 1]) + 1;
            }
        }
    }
    
    cout << memo[0][size - 1] << endl;
    return 0;
}