LCS 模型:求「最值问题」只需要确保「不漏」即可|Java 刷题打卡

简介: LCS 模型:求「最值问题」只需要确保「不漏」即可|Java 刷题打卡

题目描述



这是 LeetCode 上的 1035. 不相交的线 ,难度为 中等


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


在两条独立的水平线上按给定的顺序写下 nums1 和 nums2 中的整数。


现在,可以绘制一些连接两个数字 nums1[i] 和 nums2[j] 的直线,这些直线需要同时满足满足:


  • nums1[i] == nums2[j]
  • 且绘制的直线不与任何其他连线(非水平线)相交。


请注意,连线即使在端点也不能相交:每个数字只能属于一条连线。


以这种方法绘制线条,并返回可以绘制的最大连线数。

 

示例 1:


网络异常,图片无法展示
|


输入:nums1 = [1,4,2], nums2 = [1,2,4]
输出:2
解释:可以画出两条不交叉的线,如上图所示。 
但无法画出第三条不相交的直线,因为从 nums1[1]=4 到 nums2[2]=4 的直线将与从 nums1[2]=2 到 nums2[1]=2 的直线相交。
复制代码


示例 2:


输入:nums1 = [2,5,1,2,5], nums2 = [10,5,2,1,5,2]
输出:3
复制代码


示例 3:


输入:nums1 = [1,3,7,1,7,5], nums2 = [1,9,2,5,1]
输出:2
复制代码


提示:


  • 1 <= nums1.length <= 500
  • 1 <= nums2.length <= 500
  • 1 <= nums1[i], nums2[i] <= 2000


动态规划



这是一道「最长公共子序列(LCS)」的轻度变形题。


为了让你更好的与「最长公共子序列(LCS)」裸题进行对比,我们使用 s1s1s1 代指 nums1nums1nums1s2s2s2 代指 nums2nums2nums2


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


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


然后不失一般性的考虑 f[i][j]f[i][j]f[i][j] 如何转移。


由于我们的「状态定义」只是说「考虑前 iii 个和考虑前 jjj 个字符」,并没有说「一定要包含第 iii 个或者第 jjj 个字符」(这也是「最长公共子序列 LCS」与「最长上升子序列 LIS」状态定义上的最大不同)。


我们需要考虑「不包含 s1[i]s1[i]s1[i],不包含 s2[j]s2[j]s2[j]」、「不包含 s1[i]s1[i]s1[i],包含 s2[j]s2[j]s2[j]」「包含 s1[i]s1[i]s1[i],不包含 s2[j]s2[j]s2[j]」、「包含 s1[i]s1[i]s1[i],包含 s2[j]s2[j]s2[j]」四种情况:


  • 不包含 s1[i]s1[i]s1[i],不包含 s2[j]s2[j]s2[j]:结合状态定义,可以使用 f[i−1][j−1]f[i - 1][j - 1]f[i1][j1] 进行精确表示。
  • 包含 s1[i]s1[i]s1[i],包含 s2[j]s2[j]s2[j]:前提是 s1[i]=s2[j]s1[i] = s2[j]s1[i]=s2[j],可以使用 f[i−1][j−1]+1f[i - 1][j - 1] + 1f[i1][j1]+1 进行精确表示。
  • 不包含 s1[i]s1[i]s1[i],包含 s2[j]s2[j]s2[j]:结合状态定义,我们无法直接将该情况表示出来。注意 f[i−1][j]f[i - 1][j]f[i1][j] 只是表示「必然不包含 s1[i]s1[i]s1[i],但可能包含s2[j]s2[j]s2[j]」的情况,也就是说 f[i−1][j]f[i - 1][j]f[i1][j] 其实是该情况与情况 111 的合集。 但是由于我们求的是「最大值」,只需要确保「不漏」即可保证答案的正确(某些情况被重复参与比较不影响正确性),因此这里直接使用 f[i−1][j]f[i - 1][j]f[i1][j] 进行表示没有问题。
  • 包含 s1[i]s1[i]s1[i],不包含 s2[j]s2[j]s2[j]:与情况 333 同理,直接使用 f[i][j−1]f[i][j - 1]f[i][j1] 表示没有问题。


f[i][j]f[i][j]f[i][j] 就是在上述所有情况中取 maxmaxmax 而来,由于情况 111 被 情况 333 和 情况 444 所包含,因此我们只需要考虑 f[i−1][j]f[i - 1][j]f[i1][j]f[i][j−1]f[i][j -1]f[i][j1]f[i−1][j−1]+1f[i - 1][j - 1] + 1f[i1][j1]+1 三种状态即可,其中最后一种状态需要满足 s1[i]=s2[j]s1[i] = s2[j]s1[i]=s2[j] 前提条件。


因此我们最后的状态转移方程为:


f[i][j]={max⁡(f[i−1][j],f[i][j−1],f[i−1][j−1]+1)s1[i]=s2[j]max⁡(f[i−1][j],f[i][j−1])s1[i]≠s2[j]f[i][j]=\begin{cases} \max(f[i - 1][j], f[i][j - 1], f[i - 1][j - 1] + 1) & s1[i] = s2[j] \\ \max(f[i - 1][j], f[i][j - 1]) & s1[i] \neq s2[j] \\ \end{cases}f[i][j]={max(f[i1][j],f[i][j1],f[i1][j1]+1)max(f[i1][j],f[i][j1])s1[i]=s2[j]s1[i]=s2[j]


上述分析过程建议加深理解,估计很多同学能 AC 但其实并不知道 LCS 问题的状态转移是包含了「重复状态比较」的。


代码:


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


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


最后



这是我们「刷穿 LeetCode」系列文章的第 No.1035 篇,系列开始于 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

热门文章

最新文章