Range DP

Tutorial

Dynamic programming on ranges is a general technique used to solve problems of the form "what is the minimum/maximum metric one can achieve on an array $A$?" with the following properties:

• A greedy approach seems feasible but yields incorrect answers.
• Given the answers for each subarray $A[l : x]$ and $A[y : r]$, we can calculate the answer for the subarray $A[l : r]$ in $\mathcal O(r - l)$ time.
• Disjoint subarrays can be "combined" independently.
• $N$ (the size of $A$) is not greater than $500$.

This technique relies on the assumption that we can "combine" two subarrays $A[l : x]$ and $A[x + 1 : r]$ to get a candidate for $A[l : r]$. We can thus iterate over all $x$ and find the best possible answer for $A[l : r]$. (Note that we need to process subarrays in increasing order of length!)

Since there are $\mathcal O(N^2)$ subarrays and processing each one takes $\mathcal O(N)$ time, solutions using this technique generally run in $\mathcal O(N^3)$ time.

Solution - Space Jazz

Time Complexity: $\mathcal O(N^3)$

While it may be tempting to use a greedy approach (e.g. repeatedly erasing matching letters until you can't anymore, and then erasing the first "bad" letter), this approach doesn't work on inputs like ababa. Combined with the fact that $N \leq 500$ here, this suggests that we should use dynamic programming on ranges.

Let's consider the above test case - which a (if any) should we match the first letter with? Since $N$ is small, we may as well try each other a, but then how do we deal with the resulting "gaps" in the string?

The key observation is that if we match it with the second a in the string, then we can't match the two bs together. This means that we don't actually need to care about the gaps from matching letters! More specifically, if it's optimal to match $S[0]$ with $S[i]$, then the minimum number of insertions for $S$ is the sum of the minimum number of insertions for $S[1 : i - 1]$ and $S[i + 1 : |S| - 1]$.

We can thus use dynamic programming on ranges to find, for each substring of $S$, the minimum number of insertions needed to turn it into space jazz.

(Don't forget to consider the case where we don't match $S[i]$ with anything, and just duplicate it!)

Copy
#include <bits/stdc++.h>
using namespace std;

int dp[502][502];  // Min additions to get "jazz" from index i to j
                   // Inclusive and 0-indexed

int main() {
	cin.tie(0)->sync_with_stdio(0);
	string s;
	cin >> s;

Copy
import java.io.*;
import java.util.*;

public class Jazz {
	public static final int MAXN = 500;
	public static void main(String[] args) throws IOException {
		Kattio io = new Kattio();
		char[] inp = io.next().toCharArray();

		// DP[i][j] is the min number of additions to get "jazz" from index i to

Copy
s = input()
n = len(s)
dp = [[0] * (n + 1) for _ in range(n + 1)]

for i in range(n + 1):
	for j in range(n - i):
		dp[j][i + j] = dp[j + 1][i + j] + 1
		for k in range(j + 1, i + j + 1):
			if s[k] == s[j]:
				dp[j][i + j] = min(dp[j][i + j], dp[j + 1][k - 1] + dp[k + 1][i + j])

print(dp[0][n - 1])

Problems