C#最长公共子序列详解（LCS动态规划算法从入门到实战）

为什么用动态规划？

暴力枚举所有子序列的时间复杂度极高（指数级），而C#字符串匹配中的LCS问题具有最优子结构和重叠子问题特性，非常适合用动态规划（Dynamic Programming, DP）高效解决。

动态规划思路解析

假设我们有两个字符串：str1（长度为 m）和 str2（长度为 n）。

我们定义一个二维数组 dp[i, j] 表示：str1 的前 i 个字符 与 str2 的前 j 个字符 的最长公共子序列长度。

状态转移方程如下：

• 如果 str1[i-1] == str2[j-1]，则：
  dp[i, j] = dp[i-1, j-1] + 1
• 否则：
  dp[i, j] = Math.Max(dp[i-1, j], dp[i, j-1])

C#代码实现

下面是一个完整的 C# 控制台程序，用于计算两个字符串的 LCS 长度：

using System;public class LCSExample{    public static int FindLCSLength(string str1, string str2)    {        int m = str1.Length;        int n = str2.Length;        // 创建 (m+1) x (n+1) 的 DP 表        int[,] dp = new int[m + 1, n + 1];        // 填充 DP 表        for (int i = 1; i <= m; i++)        {            for (int j = 1; j <= n; j++)            {                if (str1[i - 1] == str2[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];    }    public static void Main()    {        string s1 = "ABCDGH";        string s2 = "AEDFHR";                int lcsLength = FindLCSLength(s1, s2);        Console.WriteLine($"字符串 '{s1}' 和 '{s2}' 的最长公共子序列长度为: {lcsLength}");        // 输出: 3 （公共子序列为 "ADH"）    }}

算法复杂度分析

• 时间复杂度：O(m × n)，其中 m 和 n 分别是两个字符串的长度。
• 空间复杂度：O(m × n)，用于存储 DP 表。可通过滚动数组优化至 O(min(m, n))。

总结

通过本教程，你已经掌握了如何使用C#动态规划来解决C#最长公共子序列问题。LCS 是理解动态规划思想的绝佳入门案例，也是LCS算法实现在实际工程中（如C#字符串匹配）的重要应用。建议你动手运行代码，尝试修改输入字符串，观察结果变化，加深理解！

小提示：若想输出具体的 LCS 字符串（而不仅是长度），可在填充 DP 表后，从 dp[m,n] 开始反向回溯构造结果。