首页 > 其他分享 >【DP】LeetCode 1143. 最长公共子序列

【DP】LeetCode 1143. 最长公共子序列

时间:2023-04-22 16:56:03浏览次数:48  
标签:1143 int s2 s1 DP 数组 序列 LeetCode dp

题目链接

1143. 最长公共子序列

思路

分析动态规划题目的时候只需要考虑最后一个阶段,因为所有的阶段转化都是相同的,考虑最后一个阶段容易发现规律

在数组的动态规划问题中,一般 dp[i] 都是表示以 nums 以前 i 个元素组成(即 nums[i - 1])的状态;dp[i][j] 分别表示以 nums1 前 i 个元素(即 nums1[i - 1])组成和以 nums2 前 j 个元素(即 nums2[j - 1])组成的状态,以此类推

字符串也是个数组,是字符数组

表示状态

状态表示就是靠猜,但是会有猜的套路,一般都是通过最终结果和数组数量来猜

使用 \(dp[i][j]\) 表示 \(nums1\) 前 i 个元素和 \(nums2\) 前 j 个元素中最长的公共子序列长度

找状态转移方程

思考的方向是:大问题的最优解怎么由小问题的最优解得到

因为是找公共子序列,那么很显然要有判断字符是否相等的过程,那么我们可以分为两种情况讨论:

  1. \(s1[i]=s2[j]\) : \(dp[i][j]=dp[i−1][j−1]+1\)。代表必然使用 s1[i] 与 s2[j] 时 LCS 的长度。
  2. \(s1[i] \neq s2[j]\) : \(dp[i][j] = \max(dp[i - 1][j], dp[i][j - 1])\)。代表必然不使用 \(s1[i]\) (但可能使用 \(s2[j]\))和必然不使用 \(s2[j]\)(但可能使用 \(s1[i]\))时 LCS 的长度。

所以状态转移方程为:

\[dp[i][j] = \left\{ \begin{aligned} & dp[i - 1][j - 1] + 1, & s[i] = s[j], \\ & \max(dp[i - 1][j], dp[i][j - 1]), & s[i] \neq s[j]. \end{aligned} \right. \]

边界处理

整个 dp 数组初始化为0

代码

dp数组版

class Solution {
    public int longestCommonSubsequence(String text1, String text2) {
        int n1 = text1.length();
        int n2 = text2.length();
        int[][] dp = new int[n1 + 1][n2 + 1];

        for(int i = 1; i <= n1; i++){
            for(int j = 1; j <= n2; j++){
                if(text1.charAt(i - 1) == text2.charAt(j - 1)){
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                }else{
                    // s1[i] != s2[j] 表示:必然不使用 s1[i] (但可能使用 s2[j])或者必然不使用 s2[j] (但可能使用 s1[i])
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
                }
            }
        }

        return dp[n1][n2];
    }
}

标签:1143,int,s2,s1,DP,数组,序列,LeetCode,dp
From: https://www.cnblogs.com/shixuanliu/p/17343264.html

相关文章

  • 20220626leetcode周赛(前3道)
    title:20220622leetcode周赛(前3道)第一题,难度:简单6101.判断矩阵是否是一个X矩阵题目描述:如果一个正方形矩阵满足下述全部条件,则称之为一个X矩阵:矩阵对角线上的所有元素都不是0矩阵中所有其他元素都是0给你一个大小为nxn的二维整数数组grid,表示一个正方形......
  • leetcode200.岛屿数量
    title:leetcode200.岛屿数量题目描述:给你一个由'1'(陆地)和'0'(水)组成的的二维网格,请你计算网格中岛屿的数量。岛屿总是被水包围,并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。此外,你可以假设该网格的四条边均被水包围。示例1:输入:grid=[["1","1","1","......
  • 【DP】LeetCode 718. 最长重复子数组
    题目链接718.最长重复子数组思路分析动态规划题目的时候只需要考虑最后一个阶段,因为所有的阶段转化都是相同的,考虑最后一个阶段容易发现规律在数组的动态规划问题中,一般dp[i]都是表示以nums以第i个元素组成(即nums[i-1])的状态;dp[i][j]分别表示以nums1前i个元素(......
  • AntdPro中formItemProps和fieldProps的区别
    title:AntdPro中formItemProps和fieldProps的区别date:2023-04-1312:50:23tags:["React","AntDesign"]categories:["前端篇"]最近在工作中接触到了antd和antdpro,作为一个react和antd新人,在学习和使用中遇到了不少的问题,下边就常见的一个问题来进行记录,后......
  • #yyds干货盘点# LeetCode程序员面试金典:最长有效括号
    题目:给你一个只包含'(' 和')' 的字符串,找出最长有效(格式正确且连续)括号子串的长度。 示例1:输入:s="(()"输出:2解释:最长有效括号子串是"()"示例2:输入:s=")()())"输出:4解释:最长有效括号子串是"()()"示例3:输入:s=""输出:0代码实现:classSolution{publicint......
  • #yyds干货盘点# LeetCode面试题:删除排序链表中的重复元素
    1.简述:给定一个已排序的链表的头 head , 删除所有重复的元素,使每个元素只出现一次 。返回已排序的链表 。 示例1:输入:head=[1,1,2]输出:[1,2]示例2:输入:head=[1,1,2,3,3]输出:[1,2,3]2.代码实现:classSolution{publicListNodedeleteDuplicates(ListNodehead){......
  • 【LeetCode动态规划#11】打家劫舍系列题(涉及环结构和树形DP的讨论)
    打家劫舍力扣题目链接(opensnewwindow)你是一个专业的小偷,计划偷窃沿街的房屋。每间房内都藏有一定的现金,影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统,如果两间相邻的房屋在同一晚上被小偷闯入,系统会自动报警。给定一个代表每个房屋存放金额的非负整数数组......
  • java如何使用线程池 new threadPoolExecutor()
    //使用线程池不返回结果脚本中使用的ClassB{privatestaticfinalExecutorServiceexecutor=newThreadPoolExecutor(4,10,3000L,TimeUnit.MILLISECONDS,newArrayBlockingQueue<>(500),newThreadFactoryBuilder().setNameFormat("publish-pool-%d").build(),(......
  • 【总结】浅刷leetcode,对于位运算提高性能的一些总结
    目录什么是位运算?位运算技巧1.判断奇偶性2.交换两个数3.判断一个数是否是2的幂次方4.取绝对值5.计算平均数结论位运算技巧是计算机科学中非常重要的一部分,它可以用来解决很多实际问题。在本篇博客中,我们将介绍一些常见的位运算技巧,以及它们在实际应用中的使用。什......
  • golang中通过原始socket实现tcp/udp的服务端和客户端示例
    这些天稍微空点,总结下golang中通过tcp/udp实现服务端客户端的编程实现,毕竟长久以来,如果要截单的http服务,我们直接使用net/http包实现服务,或者使用框架如gin/echo/beego等。以下就直接上代码,稍微看看都能懂起。1.TCP的实现serverpackagemainimport( "bufio" "fmt" "net"......