解题思路

这是一个经典的最长公共子序列（Longest Common Subsequence, LCS）问题。两层楼的饭店序列用两个字符串表示，要求“同时出现且顺序一致”的最大个数，恰好就是两字符串的 LCS 长度（注意子序列可以不连续，但相对顺序必须一致）。

设字符串分别为 $s$ 与 $t$，长度为 $n,m$。定义动态规划：

• 状态：$dp[i][j]$ 表示 $s$ 的前 $i$ 个字符与 $t$ 的前 $j$ 个字符的 LCS 长度。

• 转移：

  • 若 $s[i-1]=t[j-1]$，则 $dp[i][j]=dp[i-1][j-1]+1$；

题目内容

华华酒店因许多重复的饭店同时出现在一二层，影响装修美观，现需对 $1,2$ 层的饭店进行管理。需找到两层之间都出现过，且出现顺序都一致的饭馆的个数。

管理规则: 每一层用一个字符串表示。每间饭店用 $('a-z')$ 任意一个字母表示，同层饭店的字母可能重复出现，不同层字母顺序不一致。现需找到两层之间都出现过，且出现顺序都一致的饭店的个数。例如:第一层拥有的饭店为 “$abcbdab$”，为 $7$ 间饭店，第二层拥有的饭店为 “$bcdbda$”，为 $6$ 间饭店。找到的结果应该为 “$bcbda$” $5$ 间饭店。

输入描述

两个字符串，字符串长度均小于等于 $20$

输出描述

最长的共有饭店的个数

样例1

输入

abcbdab
bcdbda

输出

5