templates · Dynamic programming

Interval DP

  • The answer for a range [i..j] comes from smaller ranges inside it
  • "Burst", "merge" or "remove" items where the neighbours change after each step
  • Two players taking from either end, or palindromes in a substring

Interval DP

the one rule

The invariant

When the loop is at length len, every interval shorter than len already holds its final answer.

write it from memory

The template

with a split point k

javajava.util.*
/** Burst Balloons: best coins from bursting every balloon, where bursting k earns left * k * right. */static int maxCoins(int[] nums) {    int n = nums.length;    int[] v = new int[n + 2];                            // pad with a 1 on each side    v[0] = 1;    v[n + 1] = 1;    for (int i = 0; i < n; i++) v[i + 1] = nums[i];    int[][] dp = new int[n + 2][n + 2];                  // dp[i][j] = best for balloons strictly between i and j    for (int len = 2; len <= n + 1; len++) {             // short intervals first        for (int i = 0; i + len <= n + 1; i++) {            int j = i + len;            for (int k = i + 1; k < j; k++) {            // k = the LAST balloon to burst in (i, j)                int value = dp[i][k] + v[i] * v[k] * v[j] + dp[k][j];                dp[i][j] = Math.max(dp[i][j], value);            }        }    }    return dp[0][n + 1];                                 // the whole row}

Choose k as the last balloon to burst, not the first. Then its neighbours are fixed (i and j), and the two sides do not affect each other.

fill in the blanks — only these lines change per problem

  1. line 8What an interval's cell means, and whether the ends are inclusive or (as here) open.
  2. line 9Loop by interval length, short to long (or i from the end down). Looping i from 0 upwards reads cells that are not ready yet.
  3. line 12What k stands for: the last item removed, the place to cut, or the root of a subtree.
  4. line 13Cost of the two halves plus the cost of k itself, with max or min around it.

look at the two ends

javajava.util.*
/** Longest Palindromic Subsequence: no split point, each interval looks at its two ends. */static int longestPalindromeSubseq(String s) {    int n = s.length();    if (n == 0) return 0;    int[][] dp = new int[n][n];                          // dp[i][j] = answer for s[i..j]    for (int i = 0; i < n; i++) dp[i][i] = 1;            // base case: one letter    for (int len = 2; len <= n; len++) {        for (int i = 0; i + len - 1 < n; i++) {            int j = i + len - 1;            if (s.charAt(i) == s.charAt(j)) dp[i][j] = dp[i + 1][j - 1] + 2; // both ends join            else dp[i][j] = Math.max(dp[i + 1][j], dp[i][j - 1]);           // drop one end        }    }    return dp[0][n - 1];}

No k here: each interval only peeks at s[i] and s[j], then uses a range one or two shorter.

fill in the blanks — only these lines change per problem

  1. line 10What happens when both ends are useful together, e.g. equal letters add 2.
  2. line 6Length-1 (or length-0) intervals you can answer directly.

complexity

What it costs

time O(n³) with a split, O(n²) without
There are about n²/2 intervals. With a split point, each one tries up to n values of k; without, each is O(1).
space O(n²)
One cell per interval (i, j).

watch out

Common bugs

  • Filling the table row by row from the top, so dp[k][j] is still empty when you read it.
  • Choosing k as the first item to burst: its neighbours then depend on the other side, and the sub-problems are not independent.
  • Forgetting the padding 1s around the array, so the edges read outside it.

use it

Practise it on

learn it properly