自定义LCS递归公式是否正确？与标准公式差异分析

Great question! Let's break this down clearly: your definition will NOT produce incorrect results—it’s fully equivalent to the standard textbook LCS logic.

Let’s verify this by looking at the two core scenarios:

Scenario 1: String1[m] == String2[n] #

The textbook logic says we take LCS(m-1, n-1) + 1. Let’s see what your formulation does here: you compute the max of three values:

• LCS(m-1, n)
• LCS(m, n-1)
• LCS(m-1, n-1) + 1

Here’s the key insight: LCS(m-1, n) can never be larger than LCS(m-1, n-1) + 1. Why? The LCS of String1[1..m-1] and String2[1..n] can either include String2[n] (but since String1[m] is the only match for String2[n] here, and we’re excluding String1[m], that LCS would be equal to LCS(m-1, n-1)) or exclude it (also equal to LCS(m-1, n-1)). The maximum possible gain from adding String2[n] is 1, which is exactly what we get from LCS(m-1, n-1) +1.

The same logic applies to LCS(m, n-1)—it can’t exceed LCS(m-1, n-1) +1. So the max of the three values will always be LCS(m-1, n-1) +1, which matches the textbook logic perfectly.

Scenario 2: String1[m] != String2[n] #

The textbook logic takes max(LCS(m-1, n), LCS(m, n-1)). Your formulation adds a third term: LCS(m-1, n-1) + 0 (since the equality check fails).

But here’s why this doesn’t change anything:

• LCS(m-1, n) is always greater than or equal to LCS(m-1, n-1) (adding more characters to String2 can’t make the LCS shorter).
• LCS(m, n-1) is also always ≥ LCS(m-1, n-1) (same reasoning for String1).

So the max of the three values is just the max of LCS(m-1, n) and LCS(m, n-1)—exactly what the textbook logic returns.

Formal Proof by Induction #

To make this airtight, let’s use induction:

1. Base Case: When m=0 or n=0, the LCS is 0. Both definitions return 0, so they’re equivalent.
2. Inductive Step: Assume that for all pairs (i,j) where i < m or j < n, the two definitions produce the same result. Then:
   • If String1[m] == String2[n]: Both definitions return LCS(m-1, n-1) +1 (as shown in Scenario 1).
   • If String1[m] != String2[n]: Both definitions return max(LCS(m-1, n), LCS(m, n-1)) (as shown in Scenario 2).

By induction, the two definitions are equivalent for all non-negative integers m and n.

内容的提问来源于stack exchange，提问作者Tanay