经典 dp 模型:最长公共子序列问题|Java 刷题打卡

简介: 经典 dp 模型:最长公共子序列问题|Java 刷题打卡

题目描述



这是 LeetCode 上的 1143. 最长公共子序列 ,难度为 中等


Tag : 「最长公共子序列」、「LCS」、「序列 DP」


给定两个字符串 text1 和 text2,返回这两个字符串的最长 公共子序列 的长度。如果不存在 公共子序列 ,返回 0 。


一个字符串的 子序列 是指这样一个新的字符串:它是由原字符串在不改变字符的相对顺序的情况下删除某些字符(也可以不删除任何字符)后组成的新字符串。


  • 例如,"ace" 是 "abcde" 的子序列,但 "aec" 不是 "abcde" 的子序列。


两个字符串的 公共子序列 是这两个字符串所共同拥有的子序列。


示例 1:


输入:text1 = "abcde", text2 = "ace" 
输出:3  
解释:最长公共子序列是 "ace" ,它的长度为 3 。
复制代码


示例 2:


输入:text1 = "abc", text2 = "abc"
输出:3
解释:最长公共子序列是 "abc" ,它的长度为 3 。
复制代码


示例 3:


输入:text1 = "abc", text2 = "def"
输出:0
解释:两个字符串没有公共子序列,返回 0 。
复制代码


提示:


  • 1 <= text1.length, text2.length <= 1000
  • text1 和 text2 仅由小写英文字符组成。


动态规划【空格技巧】



这是一道「最长公共子序列(LCS)」的裸题。


对于这类题的都使用如下「状态定义」即可:


f[i][j]f[i][j]f[i][j] 代表考虑 s1s1s1 的前 iii 个字符、考虑 s2s2s2 的前 jjj 的字符,形成的最长公共子序列长度。


当有了「状态定义」之后,基本上「转移方程」就是呼之欲出:


  • s1[i]==s2[j] : f[i][j]=f[i−1][j−1]+1f[i][j]=f[i-1][j-1]+1f[i][j]=f[i1][j1]+1。代表必然使用 s1[i]s1[i]s1[i]s2[j]s2[j]s2[j] LCS 的长度。
  • s1[i]!=s2[j] : f[i][j]=max(f[i−1][j],f[i][j−1])f[i][j]=max(f[i-1][j], f[i][j-1])f[i][j]=max(f[i1][j],f[i][j1])。代表必然不使用 s1[i]s1[i]s1[i](但可能使用s2[j]s2[j]s2[j])时必然不使用 s2[j]s2[j]s2[j](但可能使用s1[i]s1[i]s1[i])时 LCS 的长度。


一些编码细节:


通常我会习惯性往字符串头部追加一个空格,以减少边界判断(使下标从 1 开始,并很容易构造出可滚动的「有效值」)。


代码:


class Solution {
    public int longestCommonSubsequence(String s1, String s2) {
        int n = s1.length(), m = s2.length();
        s1 = " " + s1; s2 = " " + s2;
        char[] cs1 = s1.toCharArray(), cs2 = s2.toCharArray();
        int[][] f = new int[n + 1][m + 1]; 
        // 因为有了追加的空格,我们有了显然的初始化值(以下两种初始化方式均可)
        // for (int i = 0; i <= n; i++) Arrays.fill(f[i], 1);
        for (int i = 0; i <= n; i++) f[i][0] = 1;
        for (int j = 0; j <= m; j++) f[0][j] = 1;
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                if (cs1[i] == cs2[j]) {
                    f[i][j] = f[i -1][j - 1] + 1;
                } else {
                    f[i][j] = Math.max(f[i - 1][j], f[i][j - 1]);
                }
            }
        }
        // 减去最开始追加的空格
        return f[n][m] - 1;
    }
}
复制代码


  • 时间复杂度:O(n∗m)O(n * m)O(nm)
  • 空间复杂度:O(n∗m)O(n * m)O(nm)


动态规划【利用偏移】



上述「追加空格」的做法是我比较习惯的做法 🤣


事实上,我们也可以通过修改「状态定义」来实现递推:


f[i][j]f[i][j]f[i][j] 代表考虑 s1s1s1 的前 i−1i - 1i1 个字符、考虑 s2s2s2 的前 j−1j - 1j1 的字符,形成的最长公共子序列长度。


那么最终的 f[n][m]f[n][m]f[n][m] 就是我们的答案,f[0][0]f[0][0]f[0][0] 当做无效值,不处理即可。


  • s1[i-1]==s2[j-1] : f[i][j]=f[i−1][j−1]+1f[i][j]=f[i-1][j-1]+1f[i][j]=f[i1][j1]+1。代表使用 s1[i−1]s1[i-1]s1[i1]s2[j−1]s2[j-1]s2[j1]形成最长公共子序列的长度。
  • s1[i-1]!=s2[j-1] : f[i][j]=max(f[i−1][j],f[i][j−1])f[i][j]=max(f[i-1][j], f[i][j-1])f[i][j]=max(f[i1][j],f[i][j1])。代表不使用 s1[i−1]s1[i-1]s1[i1] 形成最长公共子序列的长度、不使用 s2[j−1]s2[j-1]s2[j1] 形成最长公共子序列的长度。这两种情况中的最大值。


代码:


class Solution {
    public int longestCommonSubsequence(String s1, String s2) {
        int n = s1.length(), m = s2.length();
        char[] cs1 = s1.toCharArray(), cs2 = s2.toCharArray();
        int[][] f = new int[n + 1][m + 1]; 
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                if (cs1[i - 1] == cs2[j - 1]) {
                    f[i][j] = f[i - 1][j - 1] + 1;
                } else {
                    f[i][j] = Math.max(f[i - 1][j], f[i][j - 1]);
                }
            }
        }
        return f[n][m];
    }
}
复制代码


  • 时间复杂度:O(n∗m)O(n * m)O(nm)
  • 空间复杂度:O(n∗m)O(n * m)O(nm)


最后



这是我们「刷穿 LeetCode」系列文章的第 No.1143 篇,系列开始于 2021/01/01,截止于起始日 LeetCode 上共有 1916 道题目,部分是有锁题,我们将先将所有不带锁的题目刷完。


在这个系列文章里面,除了讲解解题思路以外,还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。


为了方便各位同学能够电脑上进行调试和提交代码,我建立了相关的仓库:github.com/SharingSour…


在仓库地址里,你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。

相关文章
|
2月前
|
缓存 前端开发 Java
Java类加载机制与双亲委派模型
本文深入解析Java类加载机制,涵盖类加载过程、类加载器、双亲委派模型、自定义类加载器及实战应用,帮助开发者理解JVM核心原理与实际运用。
|
2月前
|
机器学习/深度学习 人工智能 自然语言处理
Java 大视界 -- Java 大数据机器学习模型在自然语言生成中的可控性研究与应用(229)
本文深入探讨Java大数据与机器学习在自然语言生成(NLG)中的可控性研究,分析当前生成模型面临的“失控”挑战,如数据噪声、标注偏差及黑盒模型信任问题,提出Java技术在数据清洗、异构框架融合与生态工具链中的关键作用。通过条件注入、强化学习与模型融合等策略,实现文本生成的精准控制,并结合网易新闻与蚂蚁集团的实战案例,展示Java在提升生成效率与合规性方面的卓越能力,为金融、法律等强监管领域提供技术参考。
|
2月前
|
机器学习/深度学习 算法 Java
Java 大视界 -- Java 大数据机器学习模型在生物信息学基因功能预测中的优化与应用(223)
本文探讨了Java大数据与机器学习模型在生物信息学中基因功能预测的优化与应用。通过高效的数据处理能力和智能算法,提升基因功能预测的准确性与效率,助力医学与农业发展。
|
2月前
|
机器学习/深度学习 搜索推荐 数据可视化
Java 大视界 -- Java 大数据机器学习模型在电商用户流失预测与留存策略制定中的应用(217)
本文探讨 Java 大数据与机器学习在电商用户流失预测与留存策略中的应用。通过构建高精度预测模型与动态分层策略,助力企业提前识别流失用户、精准触达,实现用户留存率与商业价值双提升,为电商应对用户流失提供技术新思路。
|
2月前
|
机器学习/深度学习 存储 分布式计算
Java 大视界 --Java 大数据机器学习模型在金融风险压力测试中的应用与验证(211)
本文探讨了Java大数据与机器学习模型在金融风险压力测试中的创新应用。通过多源数据采集、模型构建与优化,结合随机森林、LSTM等算法,实现信用风险动态评估、市场极端场景模拟与操作风险预警。案例分析展示了花旗银行与蚂蚁集团的智能风控实践,验证了技术在提升风险识别效率与降低金融风险损失方面的显著成效。
|
2月前
|
机器学习/深度学习 自然语言处理 算法
Java 大视界 -- Java 大数据机器学习模型在自然语言处理中的对抗训练与鲁棒性提升(205)
本文探讨Java大数据与机器学习在自然语言处理中的对抗训练与鲁棒性提升,分析对抗攻击原理,结合Java技术构建对抗样本、优化训练策略,并通过智能客服等案例展示实际应用效果。
|
3月前
|
机器学习/深度学习 分布式计算 Java
Java 大视界 -- Java 大数据机器学习模型在遥感图像土地利用分类中的优化与应用(199)
本文探讨了Java大数据与机器学习模型在遥感图像土地利用分类中的优化与应用。面对传统方法效率低、精度差的问题,结合Hadoop、Spark与深度学习框架,实现了高效、精准的分类。通过实际案例展示了Java在数据处理、模型融合与参数调优中的强大能力,推动遥感图像分类迈向新高度。
|
3月前
|
机器学习/深度学习 存储 Java
Java 大视界 -- Java 大数据机器学习模型在游戏用户行为分析与游戏平衡优化中的应用(190)
本文探讨了Java大数据与机器学习模型在游戏用户行为分析及游戏平衡优化中的应用。通过数据采集、预处理与聚类分析,开发者可深入洞察玩家行为特征,构建个性化运营策略。同时,利用回归模型优化游戏数值与付费机制,提升游戏公平性与用户体验。
|
3月前
|
机器学习/深度学习 算法 Java
Java 大视界 -- Java 大数据机器学习模型在舆情分析中的情感倾向判断与话题追踪(185)
本篇文章深入探讨了Java大数据与机器学习在舆情分析中的应用,重点介绍了情感倾向判断与话题追踪的技术实现。通过实际案例,展示了如何利用Java生态工具如Hadoop、Hive、Weka和Deeplearning4j进行舆情数据处理、情感分类与趋势预测,揭示了其在企业品牌管理与政府决策中的重要价值。文章还展望了多模态融合、实时性提升及个性化服务等未来发展方向。
|
4月前
|
Java 数据库连接 API
Java 对象模型现代化实践 基于 Spring Boot 与 MyBatis Plus 的实现方案深度解析
本文介绍了基于Spring Boot与MyBatis-Plus的Java对象模型现代化实践方案。采用Spring Boot 3.1.2作为基础框架,结合MyBatis-Plus 3.5.3.1进行数据访问层实现,使用Lombok简化PO对象,MapStruct处理对象转换。文章详细讲解了数据库设计、PO对象实现、DAO层构建、业务逻辑封装以及DTO/VO转换等核心环节,提供了一个完整的现代化Java对象模型实现案例。通过分层设计和对象转换,实现了业务逻辑与数据访问的解耦,提高了代码的可维护性和扩展性。
168 1

热门文章

最新文章