算法基础-最长公共子序列

本文共219个字,预计阅读时间需要1分钟。

作为一个菜鸡,本文作为查询模板

一个序列 S ,如果分别是两个或多个已知序列的子序列,且是所有符合此条件序列中最长的,则 S 称为已知序列的最长公共子序列。

转移方程:

dp[i,j] = 0 i=0 || j=0

dp[i,j] = dp[i-1][j-1]+1 i>0,j>0, a[i] = b[j]

dp[i,j] = max(dp[i-1][j],dp[i][j-1]) i>0,j>0, a[i] != b[j]

 

读者评分
[评分人数: 0 平均分: 0]

评论