人工做流量的网站,购物网站最近浏览怎么做,肇庆建设工程备案的网站,国外免费舆情网站有哪些软件最长公共子序列
1143. 最长公共子序列 - 力扣#xff08;LeetCode#xff09;
代码随想录 (programmercarl.com)
最长公共子序列 - 动态规划 Longest Common Subsequence - Dynamic Programming_哔哩哔哩_bilibili
本题和上一题718.最长重复子数组在很多方面相似#xf…最长公共子序列
1143. 最长公共子序列 - 力扣LeetCode
代码随想录 (programmercarl.com)
最长公共子序列 - 动态规划 Longest Common Subsequence - Dynamic Programming_哔哩哔哩_bilibili
本题和上一题718.最长重复子数组在很多方面相似区别在与不需要连续因此在dp数组的推导上有些改变。
由于不需要连续dp[i][j]的值针对text1和text2相同及不同这两种情况有不同的表示。
首先 dp[i][j]表示序列text1[0:i-1]和text2[0:j-1]的最长公共子序列的长度
当text[i-1] text[j-1]时dp[i][j] dp[i-1][j-1]1而当text1[i-1]!text2[j-1]时dp[i][j] max(dp[i-1][j],dp[i][j-1])dp[i][j]由数组左和上的较大值确定。
由此dp[i][j]由左上部分确认当i j为0时表示的序列为空空序列与任何序列的最长公共子序列均为空长度为0dp[0][0]、dp[0][1]、dp[1][0]都为0。
ij两个变量循环遍历。
最后返回dp[text1.size()][text2.size()]。
class Solution {
public:int longestCommonSubsequence(string text1, string text2) {// 创建一个二维向量 dp用于存储动态规划的状态值// dp[i][j] 表示 text1 的前 i 个字符和 text2 的前 j 个字符的 LCS 长度// 初始化 dp 的大小为 (text1.size()1) x (text2.size()1)值全部为 0vectorvectorint dp(text1.size() 1, vectorint(text2.size() 1, 0));// 双层循环遍历 text1 和 text2for (int i 1; i text1.size(); i) { // i 从 1 开始直到 text1.size()for (int j 1; j text2.size(); j) { // j 从 1 开始直到 text2.size()// 如果 text1 的第 i 个字符和 text2 的第 j 个字符相同if (text1[i - 1] text2[j - 1]) {// 则 dp[i][j] 等于 dp[i-1][j-1] 加 1dp[i][j] dp[i - 1][j - 1] 1;} else {// 如果不相同则 dp[i][j] 等于 dp[i-1][j] 和 dp[i][j-1] 中的较大值// 这意味着当前字符不包含在 LCS 中dp[i][j] max(dp[i - 1][j], dp[i][j - 1]);}}}// 返回 dp[text1.size()][text2.size()]即 text1 和 text2 的 LCS 长度return dp[text1.size()][text2.size()];}
算法的时间复杂度为O(m*n)空间复杂度为O(m*n)m和n分别代表两个序列的长度二维数组二维循环遍历。 不相交的线
1035. 不相交的线 - 力扣LeetCode
和上题一致换些变量便能解决不过真要面试的时候希望能想到吧。
class Solution {
public:int maxUncrossedLines(vectorint nums1, vectorint nums2) {// 创建一个二维向量 dp用于存储动态规划的状态值// dp[i][j] 表示 nums1 的前 i 个元素和 nums2 的前 j 个元素的最长公共子序列的长度// 初始化 dp 的大小为 (nums1.size()1) x (nums2.size()1)值全部为 0vectorvectorint dp(nums1.size() 1, vectorint(nums2.size() 1, 0));// 双层循环遍历 nums1 和 nums2for (int i 1; i nums1.size(); i) { // i 从 1 开始直到 nums1.size()for (int j 1; j nums2.size(); j) { // j 从 1 开始直到 nums2.size()// 如果 nums1 的第 i 个元素和 nums2 的第 j 个元素相同if (nums1[i - 1] nums2[j - 1]) {// 则 dp[i][j] 等于 dp[i-1][j-1] 加 1dp[i][j] dp[i - 1][j - 1] 1;} else {// 如果不相同则 dp[i][j] 等于 dp[i-1][j] 和 dp[i][j-1] 中的较大值// 这意味着当前元素不包含在 LCS 中dp[i][j] max(dp[i - 1][j], dp[i][j - 1]);}}}// 返回 dp[nums1.size()][nums2.size()]即 nums1 和 nums2 的 LCS 长度// 这也是不相交的直线段的最大数量return dp[nums1.size()][nums2.size()];}
算法的时间复杂度为O(m*n)空间复杂度为O(m*n)。 最大子序和
53. 最大子数组和 - 力扣LeetCode
之前用过贪心算法解这道题当子序和为负则抛弃当前子序和从下一个位置开始计算子序和。这里使用动态规划也是类似的。
由于是连续的子序和dp[i]表示到i为止的最大子序和此处应包含nums[i]
dp[i] max(dp[i-1]nums[i],nums[i])这里可以想象贪心的思路当dp[i-1]为负时自然dp[i-1]nums[i]要小于nums[i]。
因此唯一需要的是当前元素的前一位的dp值dp[0] nums[0]。
从前往后遍历
最后返回dp数组中的最大值。
class Solution {
public:int maxSubArray(vectorint nums) {// 创建一个向量 dp用于存储以第 i 个元素结尾的最大子数组和// 初始化 dp 的大小与 nums 相同值全部为 0vectorint dp(nums.size(), 0);// dp[0] 是数组第一个元素的值因为一个元素的子数组和就是它本身dp[0] nums[0];// 遍历数组 nums从第二个元素开始for (int i 1; i nums.size(); i) {// 如果以第 i-1 个元素结尾的最大子数组和小于 0if (dp[i - 1] 0) {// 则以第 i 个元素结尾的最大子数组和就是第 i 个元素的值// 因为加上前面的子数组和会使得和更小dp[i] nums[i];} else {// 如果以第 i-1 个元素结尾的最大子数组和大于等于 0// 则将第 i 个元素的值加到以第 i-1 个元素结尾的最大子数组和上// 这样可以保持子数组的连续性dp[i] dp[i - 1] nums[i];}}// 使用 STL 中的 max_element 函数找出 dp 中的最大值// 这个最大值就是整个数组的最大子数组和return *max_element(dp.begin(), dp.end());}
};算法的时间复杂度为O(n),空间复杂度为O(n)。 判断子序列
392. 判断子序列 - 力扣LeetCode
同样和最长公共子序列相似在遍历过程中当dp[i][j] s.size()时表示s为t的子序列否则s不是t的子序列具体代码如下。
class Solution {
public:// 定义一个成员函数用于判断 s 是否为 t 的子序列bool isSubsequence(string s, string t) {// 如果 s 为空字符串那么它是任何字符串的子序列if (s.size() 0) {return true;}// 创建一个二维向量 dp用于存储动态规划的状态值// dp[i][j] 表示 s 的前 i 个字符和 t 的前 j 个字符的匹配长度vectorvectorint dp(s.size() 1, vectorint(t.size() 1, 0));// 双层循环遍历 s 和 tfor (int i 1; i s.size(); i) { // i 从 1 开始直到 s.size()for (int j 1; j t.size(); j) { // j 从 1 开始直到 t.size()// 如果 s 的第 i 个字符和 t 的第 j 个字符相同if (s[i - 1] t[j - 1]) {// 则 dp[i][j] 等于 dp[i-1][j-1] 加 1dp[i][j] dp[i - 1][j - 1] 1;// 如果匹配长度等于 s 的长度说明 s 是 t 的子序列if (dp[i][j] s.size()) {return true;}} else {// 如果不相同则 dp[i][j] 等于 dp[i-1][j] 和 dp[i][j-1] 中的较大值// 这表示当前字符不包含在子序列中dp[i][j] max(dp[i - 1][j], dp[i][j - 1]);}}}// 如果遍历完 dp 数组后没有找到匹配长度等于 s 长度的状态则 s 不是 t 的子序列return false;}
};算法的时间复杂度为O(m*n)空间复杂度为O(m*n)。
