Dynamic Programming for Sequence Problems: States, Recurrences, and Base Cases

Welcome back. In the previous lesson, you chose BFS or DFS by identifying what a graph traversal must guarantee: shortest distance by layers, or exhaustive branch exploration. Dynamic programming has a similar discipline: rather than beginning with loops, begin by specifying what one subproblem means and how smaller subproblems determine it.

This lesson focuses on the core interview skill behind sequence DP: formulating a precise state, recurrence, and base cases. We will use longest increasing subsequence to establish the pattern, then derive and implement longest common subsequence in Java. Study time: about 40 minutes.

---

1. Dynamic programming is a system for reusing subproblem answers

A brute-force recursive solution often branches through many possible decisions. Dynamic programming is appropriate when different decision paths repeatedly ask for the same smaller answer.

For example, in a sequence problem, many candidate solutions may eventually need the answer to:

• “What is the best result using the first $i$ items?”
• “What is the best result that ends at index $i$?”
• “What is the best result for the first $i$ characters of one string and the first $j$ characters of another?”

Instead of recomputing that answer, DP stores it once.

The phrase state does not mean “any variable in the code.” A DP state is the minimal information that uniquely identifies a subproblem. A good state must preserve every constraint that matters for the remaining decision.

For most interview problems, derive the solution in this order:

1. Define the state in one complete sentence.
   State exactly what dp[...] represents.

2. Identify the final answer.
   It may be one particular cell, such as dp[n], or the maximum across several states.

3. Find the final decision or structural case.
   Ask: “What must be true immediately before this subproblem is solved?”

4. Write the recurrence.
   Express the current answer through smaller states.

5. State base cases.
   These are the smallest valid subproblems, not arbitrary initial values.

6. Choose an evaluation order.
   Every state referenced on the right-hand side must already be available when computing the left-hand side.

A concise formulation is more valuable in an interview than immediately producing a memorized loop:

“Let dp[i] mean ___. For state $i$, the valid preceding states are ___. Therefore the recurrence is ___. The base cases are ___. The final answer is ___.”

This short video illustrates the crucial middle of that process: choosing a sequence subproblem and generalizing its relationship to earlier subproblems.

The dependency rule determines loop order

A bottom-up DP table is not merely an array filled with nested loops. It represents a dependency structure.

If dp[i] depends only on states with smaller indices, compute left to right. If dp[i][j] depends on the row above, the cell to the left, and the diagonal, fill from the top-left toward the bottom-right. This is analogous to processing a directed acyclic graph in an order where prerequisites are already known.

---

2. One sequence: formulate an increasing-subsequence state

Consider the classic problem:

Given an integer array, find the length of its longest strictly increasing subsequence.

A subsequence preserves relative order but does not need to use adjacent elements. For example, in:

[3, 1, 5, 2, 6, 4]

[1, 2, 6] is a subsequence. So is [3, 5, 6].

A tempting but incomplete state is:

dp[i] is the best increasing subsequence in the first $i$ elements.

That state can work in some formulations, but it hides an important constraint: if you want to append nums[i], you need to know the value of the sequence’s previous final element. A more useful state makes the endpoint explicit:

State: $dp[i]$ is the length of the longest strictly increasing subsequence that ends at index $i$.

Now derive the recurrence from the final element. Any increasing subsequence ending at i either:

• consists only of nums[i], with length $1$; or
• extends a valid subsequence ending at some earlier index $j$, where $j<i$ and nums[j] < nums[i].

Therefore:

$$dp[i]=\{\begin{array}{ll}1& \text{if no earlier valid predecessor exists}\\ 1+\max dp[j]& \text{over all }j<i\text{ with }nums[j]<nums[i]\end{array}$$

The base case is built into the state definition:

$$dp[i]=1$$

initially, because every one-element subsequence is increasing.

The answer is not necessarily dp[n - 1]. The best subsequence may end anywhere, so the final answer is:

$$\underset{0\le i<n}{\max }dp[i]$$

This distinction is an interview-critical habit:

State meaning	Where is the answer?
Best result using a prefix	Often the last state
Best result ending at a particular index	Usually the maximum across states
Best result for two complete prefixes	Usually the bottom-right table cell

---

3. Two sequences: longest common subsequence

Now consider a two-sequence problem:

Given strings a and b, find the length of their longest common subsequence.

A subsequence preserves character order but can skip characters. For example:

a = "ACADB"
b = "CBDA"

"CD" is a common subsequence of length $2$. "CA" is also one. A substring would require contiguity; LCS does not.

With two sequences, one index is not enough. We need to know how much of each string is available.

State: $dp[i][j]$ is the length of the longest common subsequence between the first $i$ characters of a and the first $j$ characters of b.

This definition deliberately uses prefix lengths, not direct character indices. Thus:

• dp[0][j] compares an empty prefix of a with a prefix of b;
• dp[i][0] compares a prefix of a with an empty prefix of b;
• dp[i][j] compares a.charAt(i - 1) with b.charAt(j - 1).

The extra row and column make the boundary conditions natural.

Base cases: an empty string has no nonempty common subsequence

If either prefix is empty, the LCS has length $0$:

$$dp[0][j]=0$$ $$dp[i][0]=0$$

for every valid $i$ and $j$.

These are meaningful claims about the problem. They also prevent invalid accesses such as dp[-1][j].

Recurrence: match or mismatch

At state $dp[i][j]$, compare the final characters of the two active prefixes.

Case 1: the characters match

If:

$$a[i-1]=b[j-1]$$

then that common character can extend the LCS of the two shorter prefixes:

$$dp[i][j]=dp[i-1][j-1]+1$$

The diagonal state represents both prefixes with their final character removed.

Case 2: the characters do not match

If:

$$a[i-1]\ne b[j-1]$$

then a common subsequence cannot use both current final characters. At least one must be excluded:

• Exclude the last character of a, giving $dp[i-1][j]$.
• Exclude the last character of b, giving $dp[i][j-1]$.

Keep the longer result:

$$dp[i][j]=\max (dp[i-1][j],dp[i][j-1])$$

Combining the cases:

$$dp[i][j]=\{\begin{array}{ll}0& \text{if }i=0\text{ or }j=0\\ dp[i-1][j-1]+1& \text{if }a[i-1]=b[j-1]\\ \max (dp[i-1][j],dp[i][j-1])& \text{otherwise}\end{array}$$

The answer for the full strings is:

$$dp[m][n]$$

where $m$ and $n$ are the string lengths.

Read the table as a grid of progressively larger prefix comparisons. Moving right includes one more character from the horizontal string; moving down includes one more character from the vertical string. A diagonal contribution occurs when the active characters match. Otherwise, the value is carried from the better prefix above or to the left.

---

4. Convert the formulation directly into Java

Once the state and recurrence are correct, the implementation is almost mechanical.

public static int longestCommonSubsequence(String a, String b) {
    int m = a.length();
    int n = b.length();

    int[][] dp = new int[m + 1][n + 1];

    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (a.charAt(i - 1) == b.charAt(j - 1)) {
                dp[i][j] = dp[i - 1][j - 1] + 1;
            } else {
                dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
            }
        }
    }

    return dp[m][n];
}

The array’s default zero initialization correctly establishes all base cases:

dp[0][j] = 0
dp[i][0] = 0

The loops begin at 1 because states on row 0 or column 0 are already known. At each inner-loop iteration, all dependencies are available:

Current state	Required earlier states	Why they are available
dp[i][j] on a match	dp[i - 1][j - 1]	It is in a completed earlier row
dp[i][j] on a mismatch	dp[i - 1][j]	It is in a completed earlier row
dp[i][j] on a mismatch	dp[i][j - 1]	It was computed earlier in the current row

Why the recurrence is correct

A brief correctness explanation is useful in an interview.

Match case. If the last characters of the active prefixes are equal, one optimal common subsequence can include that shared character. Everything before it must be a common subsequence of the two shorter prefixes. Thus the best length is the diagonal answer plus one.

Mismatch case. If the active final characters differ, no common subsequence can include both of them at its end. Any valid common subsequence must omit the final character from at least one string, so it is represented by either the prefix above or the prefix to the left. Taking the maximum preserves the best option.

Complexity

For strings of lengths $m$ and $n$:

$$\text{Time}=O(mn)$$

There are $m\times n$ non-base cells, and each takes constant time to compute.

$$\text{Space}=O(mn)$$

The full table is useful while learning, debugging, and later reconstructing an actual subsequence rather than just its length.

Three frequent implementation mistakes

1. Confusing DP indices with string indices

   dp[i][j] represents prefixes of length $i$ and $j$, but Java strings are zero-indexed:

   a.charAt(i - 1)
   b.charAt(j - 1)
   

2. Allocating m by n instead of (m + 1) by (n + 1)

   The extra row and column encode empty-prefix base cases cleanly.

3. Returning a maximum over the table

   For this state definition, the complete problem is exactly dp[m][n]. The maximum-over-all-cells pattern belongs to states such as “best subsequence ending at index $i$,” not prefix-pair states.

---

5. A practical formulation checklist

When you encounter a new sequence DP question, resist the urge to immediately draw a table. First write these four lines on paper or in comments:

State:
dp[...] means ...

Choices or cases:
The final decision is ...

Recurrence:
dp[...] = ...

Base cases and answer:
...

For LCS, that becomes:

State:
dp[i][j] = LCS length of the first i characters of a
           and the first j characters of b.

Cases:
The final characters match, or they do not.

Recurrence:
Match:    dp[i][j] = dp[i - 1][j - 1] + 1
Mismatch: dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])

Base cases and answer:
dp[0][j] = dp[i][0] = 0
Answer = dp[m][n]

Notice how the wording of the state determines every later design decision:

• It tells you the table dimensions.
• It tells you what each index means.
• It tells you which result to return.
• It exposes valid predecessor states.
• It prevents accidental use of an invalid recurrence.

---

Key takeaways

Dynamic programming starts with a precise subproblem definition, not with code.

• A state uniquely identifies a smaller version of the problem.
• A recurrence explains how a state is built from strictly smaller states.
• Base cases define the smallest valid subproblems and anchor the recurrence.
• The DP fill order must ensure every dependency has already been computed.
• For one sequence, “best result ending at index $i$” is often a powerful state.
• For two sequences, prefix-pair states such as $dp[i][j]$ naturally lead to a two-dimensional table.
• In LCS, matching final characters use the diagonal plus one; mismatches take the maximum of excluding one final character from either sequence.

Next, you will shift from algorithmic interview patterns to Java concurrency, beginning with how Java’s happens-before rules and synchronization expose race conditions in an execution trace.