K12教育赛事综合服务平台
聚乐之家官方网站
下载聚乐之家官方App
专注青少年竞赛题库网站
最长公共子序列（LCS）是经典的动态规划应用场景，合理的状态表示是推导状态转移方程的基础。
设dp[i][j]表示字符串s的前i个字符与字符串t的前j个字符的最长公共子序列的长度
dp[i][j]
s
i
t
j
设dp[i][j]表示字符串s的第i个字符与字符串t的第j个字符是否为公共子序列中的一对匹配字符
设dp[i]表示字符串s的前i个字符与原字符串t的最长公共子序列长度
dp[i]
设dp[i][j]表示s的前i个字符组成的子串与t的前j个字符组成的子串的总字符数