So far you have seen DP states shaped like dp[i] (best answer for the prefix ending at i) and dp[i][j] (best answer for two strings up to positions i and j). This lesson introduces a third shape: dp[i][j] meaning "the answer for the substring or subarray from index i to index j." Both indices live inside the same sequence, and the state describes a window of that sequence rather than a prefix of it.

The cleanest entry point to this idea is palindrome DP. A palindrome is a string that reads the same forward and backward. The natural question is: which substrings of a string s are palindromes? Storing the answer for every substring is exactly an (i, j) table.

The Recurrence

Define dp[i][j] to be true if s[i..j] is a palindrome and false otherwise. The recurrence captures one observation: a string is a palindrome exactly when its outer characters match AND the substring inside them is also a palindrome.

dp[i][j] = (s[i] == s[j]) AND dp[i + 1][j - 1]

Two base cases anchor the recursion:

• Length 1 - Every single character is trivially a palindrome. dp[i][i] = true for all i.
• Length 2 - A two-character substring is a palindrome only when both characters are equal. dp[i][i + 1] = (s[i] == s[i + 1]).

For lengths 3 and up, the recurrence kicks in. The interesting bit is the order in which you fill the table.

Why Diagonal Order Matters

Look at the recurrence again. To compute dp[i][j], you need dp[i + 1][j - 1] - the substring with its endpoints peeled off, which is two characters shorter. That means shorter substrings must be solved before longer ones. If you naively iterate i from 0 to n and j from i to n, you may try to read dp[i + 1][j - 1] before it has been filled.

The fix is to fill the table by interval length rather than by row or column. Start with length 1, then length 2, then length 3, all the way up to length n. Within each length, sweep i from 0 to n - length, computing j = i + length - 1. This guarantees that any subproblem you read has already been solved.

Trace on "abba"

Walk through the algorithm on s = "abba" (n = 4) so the diagonal pattern becomes concrete.

Notice how dp[0][3] only succeeds because dp[1][2] (for "bb") was already filled when we got there. That is the diagonal order at work.

Longest Palindromic Substring

Once you have the palindrome table, finding the longest palindromic substring is a small extra pass: track the (i, j) pair with the largest j - i + 1 where dp[i][j] is true. You can fold this directly into the table-filling loop and skip storing the full table if you only need the answer.

The total work is O(n^2) - every (i, j) cell does O(1) work. Space is also O(n^2). For long strings you can drop to O(1) extra space using the "expand around center" trick, but the DP table approach scales naturally to richer questions like counting palindromic substrings or building palindrome partitioning solutions on top.

Watch the table expand diagonal by diagonal to find the longest palindromic substring:

See how each true cell in the palindrome table corresponds to one palindromic substring:

Palindrome DP is the simplest member of a much larger family called interval DP. The defining feature: the state dp[i][j] represents the optimal answer for the subarray or substring arr[i..j], and the recurrence considers ways to split that interval into smaller intervals that have already been solved.

The split-point search is what makes interval DP feel different from prefix DP. Instead of recurring on dp[i - 1], you recur on every possible dp[i][k] and dp[k + 1][j] pair and pick the best.

The Generic Template

Three pieces customize this template for any specific problem:

1. Base case - what the answer is for a single element interval.
2. Split formulation - how splitting at position k combines the left and right answers.
3. Merge cost - the additional cost of joining the two halves at split point k.

Time complexity is O(n^3): O(n^2) intervals times O(n) split points each. Space is O(n^2) for the table.

Worked Example: Matrix Chain Multiplication

Given a sequence of matrices with dimensions dims = [d_0, d_1, ..., d_n] (so matrix i has shape dims[i] x dims[i+1]), find the parenthesization that minimizes the total scalar multiplications. Multiplying an a x b matrix by a b x c matrix costs a * b * c scalar operations and produces an a x c result.

Define dp[i][j] as the minimum scalar multiplications to multiply matrices i through j (inclusive). For a single matrix, no multiplication is needed: dp[i][i] = 0. For longer chains, try every split point k: multiply matrices i..k into one matrix (dp[i][k] cost), multiply matrices k+1..j into another (dp[k+1][j] cost), then multiply those two results (dims[i] * dims[k + 1] * dims[j + 1] cost).

For dims = [10, 30, 5, 60] (three matrices: 10x30, 30x5, 5x60), the two parenthesizations are:

• (A1 * A2) * A3 - first product costs 10 * 30 * 5 = 1500, then 10 * 5 * 60 = 3000. Total 4500.
• A1 * (A2 * A3) - first product costs 30 * 5 * 60 = 9000, then 10 * 30 * 60 = 18000. Total 27000.

The DP correctly returns 4500 by trying both splits and picking the cheaper one. With more matrices the number of parenthesizations grows exponentially (Catalan numbers), but the DP collapses them into O(n^3) work because subproblems overlap heavily.

Palindrome Partitioning Cuts

Another classic interval-flavored problem: given a string s, find the minimum number of cuts so every piece is a palindrome. This combines the palindrome table from the previous section with a 1D cut DP.

Let cuts[i] be the minimum cuts needed for the prefix s[0..i]. If s[0..i] is itself a palindrome, cuts[i] = 0. Otherwise, try every j from 1 to i: if s[j..i] is a palindrome, then cuts[i] = min(cuts[i], cuts[j - 1] + 1).

The pattern is: build a 2D interval table for the underlying property, then run a 1D DP on top of it that consumes the table. This layering shows up repeatedly in interval problems.

Knapsack problems are a different family of DP, but they share the spirit of interval and string DPs: you classify subproblems by a small set of indices and fill a table by following a clear dependency order. The classic 0/1 knapsack asks: given items with weights and values and a knapsack with capacity W, choose a subset of items to maximize total value without exceeding W. Each item is included or excluded - fractional choices are not allowed.

The 0/1 Knapsack Recurrence

Define dp[i][w] as the maximum value achievable using items 0..i (inclusive) with total weight at most w. For each item i, you have two choices:

• Exclude - the answer is dp[i - 1][w] (best you can do without item i).
• Include - only possible if weights[i] \<= w. The answer is dp[i - 1][w - weights[i]] + values[i] (the best value using earlier items with the remaining capacity, plus the value of item i).

Take whichever is larger:

dp[i][w] = max(dp[i - 1][w],
               dp[i - 1][w - weights[i]] + values[i])  if weights[i] <= w
         = dp[i - 1][w]                                 otherwise

The base row dp[-1][w] = 0 for all w (no items, zero value).

Time complexity is O(n * capacity). Space is also O(n * capacity), but you can compress it.

Space Compression to One Row

Each row of the table only depends on the row immediately above it. You can throw away all earlier rows and keep a single 1D array dp[w]. The trick is to iterate the inner capacity loop from right to left:

Why right to left? When you compute dp[w], the value dp[w - w_i] should refer to the previous row (item i not yet considered). Iterating left to right would overwrite dp[w - w_i] before you read it, effectively allowing item i to be picked twice. Right to left preserves the previous-row values until they are consumed.

Try it on a tiny example. Items weights = [1, 2], values = [10, 20], capacity 3:

• Initial dp = [0, 0, 0, 0]
• After item 0 (w=1, v=10), iterating w from 3 down to 1: dp[3] = max(0, dp[2]+10) = 10, dp[2] = max(0, dp[1]+10) = 10, dp[1] = max(0, dp[0]+10) = 10. Now dp = [0, 10, 10, 10].
• After item 1 (w=2, v=20), iterating w from 3 down to 2: dp[3] = max(10, dp[1]+20) = 30, dp[2] = max(10, dp[0]+20) = 20. Now dp = [0, 10, 20, 30].
• Answer dp[3] = 30 (take both items, total weight 3, total value 30).

Subset Sum and Equal Partition

Many interview problems are 0/1 knapsack in disguise. Subset sum: given an array of integers and a target T, can a subset sum exactly to T? Define dp[w] as a boolean: "is it possible to form sum w using a subset of the items so far?" The recurrence becomes dp[w] = dp[w] OR dp[w - num].

Equal partition (the practice problem in the next section): can the array be split into two subsets with equal sum? If the total is odd, the answer is no. Otherwise the question reduces to subset sum with target = total / 2.

Unbounded Knapsack and Coin Change

0/1 knapsack lets you pick each item at most once. Unbounded knapsack lets you pick each item any number of times. The change is small: iterate the inner loop left to right instead of right to left, so dp[w - w_i] already includes the current item:

Coin change (minimum coins to make a target amount) is the unbounded variant where each coin denomination is an "item" you can use unlimited times. The "coin change 2" problem (count the number of ways to make change) is also unbounded knapsack but with summation instead of max.

Why Knapsack Is Pseudo-Polynomial

Knapsack runs in O(n * capacity) time. That looks polynomial, but capacity is a numeric value, not a count of inputs. If capacity is encoded in binary, increasing capacity by one bit doubles the work. So knapsack is pseudo-polynomial - polynomial in the value of the input but exponential in the input length. For small capacities (up to roughly 10^6) the algorithm runs fast in practice; for arbitrarily large capacities you need different approaches like branch and bound or meet in the middle.

You now have a kit of DP shapes: 1D prefix DP, 2D string DP, 2D interval DP, knapsack DP. Recognizing which shape a problem needs is half the battle. Here is a practical decision guide based on the questions you ask the problem statement.

The Five Common Shapes

Two more advanced shapes round out the menu - bitmask DP and tree DP - but they are usually covered in their own lessons.

Decision Questions

Walk through these questions when you face a new DP problem:

1. Is the input a single sequence or two sequences? Two sequences usually means 2D string DP (LCS, edit distance). One sequence with a 2D state often means interval DP or grid DP.
2. Does the answer depend on a contiguous subarray with both endpoints? That is the interval DP signature. The state is dp[i][j] where i and j live in the same array.
3. Are you choosing a subset under a weight or value budget? That is knapsack. The state has a "capacity" axis.
4. Are decisions sequential and independent of position? That is 1D prefix DP. Each step extends the previous step's answer.
5. Is there a 2D physical board with movement rules? That is grid DP, which is essentially 1D prefix DP in two dimensions.

Heuristics by Problem Phrase

Watch for these signal words in problem statements:

• "Maximum/minimum cost to..." with a sequence: 1D prefix DP.
• "Longest common..." between two strings: 2D string DP.
• "Number of ways to reach..." in a grid: 2D grid DP.
• "Best way to merge/split/parenthesize..." a sequence: interval DP.
• "Can we form sum X from a subset..." or "Maximum value with weight ≤ W": knapsack DP.
• "Minimum cuts" or "minimum partitions" of a sequence: a hybrid of interval property check (palindrome table) and 1D cut DP.

Sanity Checks Before You Code

Before writing any DP, answer these on paper:

1. What is the state? Be specific about what dp[i] or dp[i][j] means in plain language. If you cannot describe it clearly, you do not understand it yet.
2. What are the base cases? Single-element intervals, empty prefixes, capacity zero. Get them right or every higher cell will be wrong.
3. What is the recurrence? Write it as an equation. Confirm it reads only from cells smaller than the current state.
4. What is the iteration order? Make sure every cell you read has already been filled. Interval DP usually means length-first. Knapsack 0/1 means right-to-left inner loop.
5. What is the answer cell? Sometimes it is dp[n - 1] or dp[n][capacity], but for problems like longest palindromic substring it is the maximum across the table. Know where the answer lives.

Skipping these on a hard problem is the fastest way to write 50 lines of plausible-looking but wrong code. A two-minute paper sketch saves twenty minutes of debugging.

Practice

The three problems below cover the new shapes from this lesson. Start with palindrome partitioning to combine the palindrome table with backtracking, then attack burst balloons as a clean interval DP, and finish with partition equal subset sum to lock in the knapsack pattern.