这是一个经典的最长公共子序列(Longest Common Subsequence, LCS)问题。两层楼的饭店序列用两个字符串表示,要求“同时出现且顺序一致”的最大个数,恰好就是两字符串的 LCS 长度(注意子序列可以不连续,但相对顺序必须一致)。
设字符串分别为 s 与 t,长度为 n,m。定义动态规划:
状态:dp[i][j] 表示 s 的前 i 个字符与 t 的前 j 个字符的 LCS 长度。
转移:
华华酒店因许多重复的饭店同时出现在一二层,影响装修美观,现需对 1,2 层的饭店进行管理。需找到两层之间都出现过,且出现顺序都一致的饭馆的个数。
管理规则: 每一层用一个字符串表示。每间饭店用 (′a−z′) 任意一个字母表示,同层饭店的字母可能重复出现,不同层字母顺序不一致。现需找到两层之间都出现过,且出现顺序都一致的饭店的个数。例如:第一层拥有的饭店为 “abcbdab”,为 7 间饭店,第二层拥有的饭店为 “bcdbda”,为 6 间饭店。找到的结果应该为 “bcbda” 5 间饭店。
两个字符串,字符串长度均小于等于 20
最长的共有饭店的个数
输入
abcbdab
bcdbda
输出
5