Rare
0/16

Range DP

Authors: Michael Cao, Andi Qu

Solving the problem on every contiguous subarray of the original array.

Prerequisites

TutorialSolution - Space JazzProblems

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.

Focus Problem – try your best to solve this problem before continuing!

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!)

C++

#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;

Java

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 j

Python

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

StatusSourceProblem NameDifficultyTags
Old GoldEasy
Show TagsRange DP
GoldEasy
Show TagsRange DP
GoldEasy
Show TagsRange DP
CFEasy
Show TagsRange DP
GoldNormal
Show TagsRange DP
CSESNormal
Show TagsRange DP
CFNormal
Show TagsRange DP
SAPONormal
Show TagsRange DP
CCNormal
Show TagsRange DP
Baltic OIHard
Show TagsRange DP
PlatHard
Show TagsRange DP
PlatHard
Show TagsRange DP
PlatVery Hard
Show TagsRange DP
CEOIVery Hard
Show TagsRange DP
CF GymVery Hard
Show TagsRange DP

Join the USACO Forum!

Stuck on a problem, or don't understand a module? Join the USACO Forum and get help from other competitive programmers!