第三阶段第一课《字母王国连线战——最长公共子序列LCS》一、故事开始两位国王的密码卷轴1、很久很久以前在算法大陆上有两个国家红苹果王国和蓝莓王国2、一天两个国王发现了两份古老的密码卷轴。红苹果王国的卷轴A B C D E蓝莓王国的卷轴A X B Y C Z D E3、国王说“请找出两份卷轴中共同拥有的最长密码”4、注意不要求连续但顺序不能改变5、例如A B C D E就在两份卷轴中都出现了。6、于是密码学家们开始研究……二、什么叫公共子序列先理解两个词。1、子序列1例如ABCDE2删除一些字符后ACE仍然保持原来顺序。3这就是子序列。再比如ABD也是子序列。2、公共1意思是两个人都有。2例如字符串1ABCDE2字符串2AXBYCDE3共同拥有ABCDE4这就是公共子序列三、什么叫最长公共子序列LCS1、LCS全称Longest Common Subsequence2、中文全称最长公共子序列3、例如ABCDE和AXBYCDE最长公共子序列ABCDE长度5答案就是5四、为什么暴力枚举的方法不行1、假设ABCDE和AXBYCDE2、如果暴力枚举第一个串所有子序列2⁵ 32种长度100呢2¹⁰⁰宇宙毁灭都算不完3、所以必须使用⚔️动态规划⚔️五、先观察两个卷轴1、假设s1 ABCs2 AC2、画成表格ACABC这张表就是今天的战场六、二维DP登场1、前面学的dp[i]是一维。2、今天升级1定义dp[i][j]表示2s1前i个字符 和 s2前j个字符的最长公共子序列长度3例如dp[3][2]表示ABC和AC的LCS长度。七、最重要的问题来了1、要来到dp[i][j]怎么转移2、我们只看最后两个字符1例如ABC和AXC2最后字符C C一样3那么这两个C一定可以配对4于是前面答案加1。5状态转移dp[i][j]dp[i-1][j-1]1当s1[i] s2[j]八、字符不一样怎么办1、例如ABC和ABD2、最后C D不一样那怎么办3、国王说扔掉一个试试看1方案1扔掉C看AB和ABD2方案2扔掉D看ABC和AB3谁更好取最大4状态转移dp[i][j] max(dp[i-1][j],dp[i][j-1])当s1[i] ! s2[j]九、完整转移公式这就是LCS的核心1、如果s1[i] s2[j]那么dp[i][j]dp[i-1][j-1]1否则dp[i][j] max(dp[i-1][j],dp[i][j-1])十、手工推导例子1、字符串ABC和AC2、建立表格0AC0000A011B011C0123、最终dp[3][2] 2答案AC长度2十一、为什么可以这样理解1、把两个字符串想成两支军队。1红军A B C2蓝军A C3每次看最后两个士兵。2、如果一样AA他们握手成功长度1。3、如果不同B ≠ C就让其中一个先退场。看看谁能组成更长队伍。十二、参考代码#include iostream #include string using namespace std; int dp[1005][1005]; int main() { string s1, s2; cin s1 s2; int n s1.size(); int m s2.size(); for(int i 1; i n; i) { for(int j 1; j m; j) { if(s1[i-1] s2[j-1]) { dp[i][j] dp[i-1][j-1] 1; } else { dp[i][j] max(dp[i-1][j], dp[i][j-1]); } } } cout dp[n][m]; return 0; }十三、程序模拟1、输入ABCDE AXBYCDE2、最终ABCDE被成功匹配。3、输出5十四、LCS与LIS有什么区别1、上一课LISLDS研究一个序列内部。2、今天LCS研究两个序列之间。3、例如1LIS3 1 2 5 4找最长上升。2LCSABCDE和AXBCYE找共同部分。十五、课堂挑战挑战1求ABCD和ACBD的LCS长度。挑战2求HELLO和HERO的LCS长度。挑战3如果两个字符串完全一样ABCDE ABCDE答案是多少挑战4如果ABCDE和FGHIJ没有任何共同字符呢十六、举一反三LCS很多经典问题都是它来变形的。例如DNA序列比对比较基因相似度文章查重比较两篇文章相似程度聊天记录分析寻找共同内容游戏存档比较找相同操作路径十七、本课总结✅今天第一次学习二维DP定义dp[i][j]表示两个前缀的LCS长度✅字符相同dp[i][j]dp[i-1][j-1]1✅字符不同dp[i][j]max(dp[i-1][j],dp[i][j-1])✅最终答案dp[n][m]下节课预告下一课⚔️《宝石矿洞探险——数字三角形》⚔️我们将进入二维路径DP学习如何在地图中寻找价值最大的路线我们是从“一维DP”走向“二维DP”的重要里程碑
GESP6级C++考试语法知识（四十四、动态规划----二维DP（一、最长公共子序列（LCS））
发布时间：2026/6/2 18:05:26
第三阶段第一课《字母王国连线战——最长公共子序列LCS》一、故事开始两位国王的密码卷轴1、很久很久以前在算法大陆上有两个国家红苹果王国和蓝莓王国2、一天两个国王发现了两份古老的密码卷轴。红苹果王国的卷轴A B C D E蓝莓王国的卷轴A X B Y C Z D E3、国王说“请找出两份卷轴中共同拥有的最长密码”4、注意不要求连续但顺序不能改变5、例如A B C D E就在两份卷轴中都出现了。6、于是密码学家们开始研究……二、什么叫公共子序列先理解两个词。1、子序列1例如ABCDE2删除一些字符后ACE仍然保持原来顺序。3这就是子序列。再比如ABD也是子序列。2、公共1意思是两个人都有。2例如字符串1ABCDE2字符串2AXBYCDE3共同拥有ABCDE4这就是公共子序列三、什么叫最长公共子序列LCS1、LCS全称Longest Common Subsequence2、中文全称最长公共子序列3、例如ABCDE和AXBYCDE最长公共子序列ABCDE长度5答案就是5四、为什么暴力枚举的方法不行1、假设ABCDE和AXBYCDE2、如果暴力枚举第一个串所有子序列2⁵ 32种长度100呢2¹⁰⁰宇宙毁灭都算不完3、所以必须使用⚔️动态规划⚔️五、先观察两个卷轴1、假设s1 ABCs2 AC2、画成表格ACABC这张表就是今天的战场六、二维DP登场1、前面学的dp[i]是一维。2、今天升级1定义dp[i][j]表示2s1前i个字符 和 s2前j个字符的最长公共子序列长度3例如dp[3][2]表示ABC和AC的LCS长度。七、最重要的问题来了1、要来到dp[i][j]怎么转移2、我们只看最后两个字符1例如ABC和AXC2最后字符C C一样3那么这两个C一定可以配对4于是前面答案加1。5状态转移dp[i][j]dp[i-1][j-1]1当s1[i] s2[j]八、字符不一样怎么办1、例如ABC和ABD2、最后C D不一样那怎么办3、国王说扔掉一个试试看1方案1扔掉C看AB和ABD2方案2扔掉D看ABC和AB3谁更好取最大4状态转移dp[i][j] max(dp[i-1][j],dp[i][j-1])当s1[i] ! s2[j]九、完整转移公式这就是LCS的核心1、如果s1[i] s2[j]那么dp[i][j]dp[i-1][j-1]1否则dp[i][j] max(dp[i-1][j],dp[i][j-1])十、手工推导例子1、字符串ABC和AC2、建立表格0AC0000A011B011C0123、最终dp[3][2] 2答案AC长度2十一、为什么可以这样理解1、把两个字符串想成两支军队。1红军A B C2蓝军A C3每次看最后两个士兵。2、如果一样AA他们握手成功长度1。3、如果不同B ≠ C就让其中一个先退场。看看谁能组成更长队伍。十二、参考代码#include iostream #include string using namespace std; int dp[1005][1005]; int main() { string s1, s2; cin s1 s2; int n s1.size(); int m s2.size(); for(int i 1; i n; i) { for(int j 1; j m; j) { if(s1[i-1] s2[j-1]) { dp[i][j] dp[i-1][j-1] 1; } else { dp[i][j] max(dp[i-1][j], dp[i][j-1]); } } } cout dp[n][m]; return 0; }十三、程序模拟1、输入ABCDE AXBYCDE2、最终ABCDE被成功匹配。3、输出5十四、LCS与LIS有什么区别1、上一课LISLDS研究一个序列内部。2、今天LCS研究两个序列之间。3、例如1LIS3 1 2 5 4找最长上升。2LCSABCDE和AXBCYE找共同部分。十五、课堂挑战挑战1求ABCD和ACBD的LCS长度。挑战2求HELLO和HERO的LCS长度。挑战3如果两个字符串完全一样ABCDE ABCDE答案是多少挑战4如果ABCDE和FGHIJ没有任何共同字符呢十六、举一反三LCS很多经典问题都是它来变形的。例如DNA序列比对比较基因相似度文章查重比较两篇文章相似程度聊天记录分析寻找共同内容游戏存档比较找相同操作路径十七、本课总结✅今天第一次学习二维DP定义dp[i][j]表示两个前缀的LCS长度✅字符相同dp[i][j]dp[i-1][j-1]1✅字符不同dp[i][j]max(dp[i-1][j],dp[i][j-1])✅最终答案dp[n][m]下节课预告下一课⚔️《宝石矿洞探险——数字三角形》⚔️我们将进入二维路径DP学习如何在地图中寻找价值最大的路线我们是从“一维DP”走向“二维DP”的重要里程碑
![构建基于Merlinite-7B-pt的问答系统：从数据准备到部署上线的完整指南 [特殊字符]](http://pic.xiahunao.cn/yaotu/构建基于Merlinite-7B-pt的问答系统：从数据准备到部署上线的完整指南 [特殊字符])
