# Range DP

Authors: Michael Cao, Andi Qu

### Prerequisites

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

## 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 – read through 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;

## Problems

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

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

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

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

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

SAPO | 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 | |||||||

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