代码随想录算法训练营第五十七天|1143.最长公共子序列、1035.不相交的线、53. 最大子序和、392.判断子序列
代码随想录算法训练营第五十七天 1143.最长公共子序列 题目链接：1143.最长公共子序列 确定dp数组以及下标的含义：dp[i][j] ：以下标i - 1为结尾的text1，和以下标j - 1为结尾的text2，最长重复子数组长度为dp[i][j]确定递推公式： 当text1[i - 1] 和text2[j - 1]相等的时候，dp[i][j] = dp[i - 1][j - 1] + 1; 那就...
【C++算法】线性DP详解：数字三角形、最长上升子序列、最长公共子序列、最长公共子串、字符串编辑距离
文章目录 1）数字三角形1：顺推2：逆推 2）最长上升子序列1：线性DP做法2：二分优化 3）最长公共子序列4）最长公共子串5）字符串编辑距离 1）数字三角形 1：顺推 顺推比较需要注意的问题就是边界问题，因为从上往下推每个元素会用到上方元素和左上方元素 对于某一行的最后一个元素，那么上方的元素是没有被初始化的对于某一行的第一个元素，那么左上方的元素是没有被初始化的为了保证这两种情况一定不选择未被初始...
【leetcode面试经典150题】26.判断子序列（C++）
【题目描述】 给定字符串 s 和 t ，判断 s 是否为 t 的子序列。 字符串的一个子序列是原始字符串删除一些（也可以不删除）字符而不改变剩余字符相对位置形成的新字符串。（例如，"ace"是"abcde"的一个子序列，而"aec"不是）。 【示例一】 输入：s = "abc", t = "ahbgdc"输出：true 【示例二】 输入：s = "axc", t = "ahbgdc"输出：fals...
day55 最长递增子序列 最长连续递增子序列 最长重复子数组
题目1 300 最长递增子序列 题目链接 300 最长递增子序列 题意 找到整数数组nums的最长严格递增子序列的长度（子序列并不改变原始的顺序，但是可以删除元素） 动态规划 动规五部曲 1）dp数组及下标i的含义 dp[i] 表示以nums[i]为结尾的最长递增子序列的长度 2）dp数组初始化 根据定义 长度至少是1 dp[i] = 1 3）递推公式 j从0到i-1各个位置的最长升序子序列 + 1...
895.最长公共子序列(acwing)
文章目录 895.最长公共子序列题目描述动态规划 895.最长公共子序列 题目描述 给定两个长度分别为 N 和 M 的字符串 A 和 B，求既是 A 的子序列又是 B 的子序列的字符串长度最长是多少。 输入格式 第一行包含两个整数 N 和 M。 第二行包含一个长度为 N 的字符串，表示字符串 A。 第三行包含一个长度为 M 的字符串，表示字符串 B。 字符串均由小写字母构成。 输出格式 输出一个整数，...
day58 回文子串 最长回文子序列
<< " " << "result=" <<result << endl; } } return result; }}; 时间复杂度：O(n^2)空间复杂度：O(n^2) 题目2：516 最长回文子序列 题目链接：516 最长回文子序列 题意 找出回文子序列的最长长度 子序列可以在不改变元素顺序的情况下，删除/不删除某个字符形成的 和647 最长回文子串的区别是，这个可以选择删除中间元素，只要不...
代码随想录算法训练营第23期day52|300.最长递增子序列、674. 最长连续递增序列、718. 最长重复子数组
目录 一、300.最长递增子序列 二、674. 最长连续递增序列 三、718. 最长重复子数组 一、300.最长递增子序列 力扣题目链接 子序列是可以在不改变原有次序的情况下删除一些元素，需要进行二重遍历进行判断 class Solution {public: int lengthOfLIS(vector<int>& nums) { if (nums.size() <= 1) return nums...
代码随想录算法训练营第23期day56|647. 回文子串、516.最长回文子序列
lse if (dp[i + 1][j - 1]) { // 情况三 result++; dp[i][j] = true; } } } } return result; }}; 二、516.最长回文子序列 力扣题目链接 class Solution {public: int longestPalindromeSubseq(string s) { vector<vector<int>> dp(s.si...
【算法|动态规划No.14】leetcode1143. 最长公共子序列
点击直接跳转到该题目 目录 1️⃣题目描述2️⃣题目解析3️⃣解题代码 1️⃣题目描述 给定两个字符串 text1 和 text2，返回这两个字符串的最长 公共子序列 的长度。如果不存在 公共子序列 ，返回 0 。 一个字符串的 子序列 是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。 例如，"ace" 是 "abcde" 的子...
【面试算法——动态规划 21】不同的子序列（hard）&& 通配符匹配（hard）
115. 不同的子序列 给你两个字符串 s 和 t ，统计并返回在 s 的 子序列 中 t 出现的个数，结果需要对 109 + 7 取模。 链接：：https://leetcode.cn/problems/distinct-subsequences/ 示例 1： 输入：s = “rabbbit”, t = “rabbit” 输出：3 解释： 如下所示, 有 3 种可以从 s 中得到 “rabbit” ...