← 返回学科目录

最长公共子序列(LCS)动态规划教学动画

通过交互式动画理解动态规划表格的填充与路径回溯过程

输入与控制
操作模式
流程控制
速度控制
当前单元格
字符匹配
LCS路径
回溯选项
动态规划表格
字符相等(来自左上)
来自上方
来自左方
当前步骤
初始化

最长公共子序列(LCS)问题:找两个序列的最长公共子序列。动态规划解法:dp[i][j]表示X前i个和Y前j个的LCS长度。递推:若X[i]=Y[j]则dp[i][j]=dp[i-1][j-1]+1;否则dp[i][j]=max(dp[i-1][j],dp[i][j-1])。

状态转移方程
dp[i][j] = dp[i-1][j-1] + 1 如果 str1[i-1] == str2[j-1]
否则取 max(dp[i-1][j], dp[i][j-1])
最长公共子序列
LCS长度:0
LCS序列:
-
就绪。请点击"生成表格"开始。