LCS算法 java

最优子结构（Optimal Substructure）

最优子结构性质是指问题的最优解可以由其子问题的最优解构造而成。换句话说，如果一个问题可以分解成若干子问题，并且这些子问题的最优解能够组合成原问题的最优解，那么这个问题就具有最优子结构性质。

最长公共子序列（LCS）

最长公共子序列问题是一个典型的具有最优子结构性质的问题。它的目标是找到两个序列的最长子序列，该子序列在两个原始序列中出现的顺序一致，但不一定是连续的。例如，序列 "ABCBDAB" 和 "BDCABA" 的最长公共子序列是 "BDAB"。

动态规划解决方案（Dynamic Programming Solution）

动态规划是一种解决具有最优子结构性质问题的有效方法。对于LCS问题，动态规划的基本思想是通过构建一个二维表格来存储子问题的解，然后利用这些子问题的解来构造原问题的解。

步骤：

1. 定义状态：

   • 设 LCS(
     标签：java,LCS,子结构,问题,算法,序列,最优,String
     From： https://blog.csdn.net/2402_82738349/article/details/139381651