leetcode 1143. 最长公共子序列【动态规划】

2024-03-10 00:44

文章标签 leetcode 动态规划最长序列 1143 公共

本文主要是介绍leetcode 1143. 最长公共子序列【动态规划】，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

leetcode 1143. 最长公共子序列
在这里插入图片描述

int longestCommonSubsequence(char* text1, char* text2) {int len1 = strlen(text1);int len2 = strlen(text2);int dp[len1 + 1][len2 + 1];memset(dp, 0, sizeof(dp));for (int i = 1; i <= len1; i++) {for (int j = 1; j <= len2; j++) {if (text1[i-1] == text2[j-1]) {dp[i][j] = dp[i - 1][j - 1] + 1;} else {dp[i][j] = fmax(dp[i - 1][j], dp[i][j - 1]);}}}return dp[len1][len2];
}

这篇关于leetcode 1143. 最长公共子序列【动态规划】的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

http://www.chinasem.cn/article/792471。 23002807@qq.com

哈希leetcode-1

目录 1前言 2.例题 2.1两数之和 2.2判断是否互为字符重排 2.3存在重复元素1 2.4存在重复元素2 2.5字母异位词分组 1前言哈希表主要是适合于快速查找某个元素（O(1)）当我们要频繁的查找某个元素，第一哈希表O(1)，第二，二分O(log n) 一般可以分为语言自带的容器哈希和用数组模拟的简易哈希。最简单的比如数组模拟字符存储，只要开26个c

第10章中断和动态时钟显示

第10章中断和动态时钟显示从本章开始，按照书籍的划分，第10章开始就进入保护模式（Protected Mode）部分了，感觉从这里开始难度突然就增加了。书中介绍了为什么有中断（Interrupt）的设计，中断的几种方式：外部硬件中断、内部中断和软中断。通过中断做了一个会走的时钟和屏幕上输入字符的程序。我自己理解中断的一些作用：为了更好的利用处理器的性能。协同快速和慢速设备一起工作

动态规划---打家劫舍

题目：你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。给定一个代表每个房屋存放金额的非负整数数组，计算你不触动警报装置的情况下，一夜之内能够偷窃到的最高金额。思路：动态规划五部曲： 1.确定dp数组及含义 dp数组是一维数组，dp[i]代表

poj3261（可重复k次的最长子串）

题意：可重复k次的最长子串解题思路：求所有区间[x,x+k-1]中的最小值的最大值。求sa时间复杂度Nlog(N),求最值时间复杂度N*N，但实际复杂度很低。题目数据也比较水，不然估计过不了。代码入下： #include<iostream>#include<algorithm>#include<stdio.h>#include<math.h>#include<cstring

poj1330（LCA最近公共祖先）

题意：求最近公共祖先思路：之前学习了树链剖分，然后我就用树链剖分的一小部分知识就可以解这个题目了，记录每个结点的fa和depth。然后查找时，每次将depth大的结点往上走直到x = y。代码如下： #include<iostream>#include<algorithm>#include<stdio.h>#include<math.h>#include<cstring>

poj 3974 and hdu 3068 最长回文串的O（n）解法(Manacher算法)

求一段字符串中的最长回文串。因为数据量比较大，用原来的O（n^2）会爆。小白上的O(n^2)解法代码：TLE啦~ #include<stdio.h>#include<string.h>const int Maxn = 1000000;char s[Maxn];int main(){char e[] = {"END"};while(scanf("%s", s) != EO

软考系统规划与管理师考试证书含金量高吗？

2024年软考系统规划与管理师考试报名时间节点：报名时间：2024年上半年软考将于3月中旬陆续开始报名考试时间：上半年5月25日到28日，下半年11月9日到12日分数线：所有科目成绩均须达到45分以上（包括45分）方可通过考试成绩查询：可在“中国计算机技术职业资格网”上查询软考成绩出成绩时间：预计在11月左右证书领取时间：一般在考试成绩公布后3~4个月，各地领取时间有所不同

uva 10131 最长子序列

题意：给大象的体重和智商，求体重按从大到小，智商从高到低的最长子序列，并输出路径。代码： #include <iostream>#include <cstdio>#include <cstdlib>#include <algorithm>#include <cstring>#include <cmath>#include <stack>#include <vect

poj 2976 分数规划二分贪心（部分对总体的贡献度） poj 3111

poj 2976：题意：在n场考试中，每场考试共有b题，答对的题目有a题。允许去掉k场考试，求能达到的最高正确率是多少。解析：假设已知准确率为x，则每场考试对于准确率的贡献值为： a - b * x，将贡献值大的排序排在前面舍弃掉后k个。然后二分x就行了。代码： #include <iostream>#include <cstdio>#incl

代码随想录冲冲冲 Day39 动态规划Part7

198. 打家劫舍 dp数组的意义是在第i位的时候偷的最大钱数是多少如果nums的size为0 总价值当然就是0 如果nums的size为1 总价值是nums[0] 遍历顺序就是从小到大遍历之后是递推公式对于dp[i]的最大价值来说有两种可能 1.偷第i个那么最大价值就是dp[i-2]+nums[i] 2.不偷第i个那么价值就是dp[i-1] 之后取这两个的最大值就是d

leetcode 1143. 最长公共子序列【动态规划】

相关文章