# Range DP

Authors: Michael Cao, Andi Qu

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

### Prerequisites

## 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 `b`

s 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-indexedint 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] + 1for 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

Status | Source | Problem Name | Difficulty | Tags | |
---|---|---|---|---|---|

Old Gold | Easy | ## Show TagsRange DP | |||

Gold | Easy | ## Show TagsRange DP | |||

Gold | Easy | ## Show TagsRange DP | |||

CF | Easy | ## Show TagsRange DP | |||

Gold | Normal | ## Show TagsRange DP | |||

CSES | Normal | ## Show TagsRange DP | |||

CF | Normal | ## Show TagsRange DP | |||

SAPO | Normal | ## Show TagsRange DP | |||

CC | Normal | ## Show TagsRange DP | |||

Baltic OI | Hard | ## Show TagsRange DP | |||

Plat | Hard | ## Show TagsRange DP | |||

Plat | Hard | ## Show TagsRange DP | |||

Plat | Very Hard | ## Show TagsRange DP | |||

CEOI | Very Hard | ## Show TagsRange DP | |||

CF Gym | Very Hard | ## Show TagsRange DP |

### Module Progress:

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