怎么做网站内部链接,库尔勒网站,上海市黄页企业名录查询,做网站，就上凡科建站代码随想录算法训练营第五十七天
1143.最长公共子序列
题目链接#xff1a;1143.最长公共子序列
确定dp数组以及下标的含义#xff1a;dp[i][j] #xff1a;以下标i - 1为结尾的text1#xff0c;和以下标j - 1为结尾的text2#xff0c;最长重复子数组长度为dp[i][j]确…代码随想录算法训练营第五十七天
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; 那就看看text1[i - 2]与text2[j - 1]的最长公共子序列 和 text1[ i - 1]与text2[j - 2]的最长公共子序列取最大的。dp[i][j] max(dp[i - 1][j], dp[i][j - 1]);if (text1[i - 1] text2[j - 1]) {dp[i][j] dp[i - 1][j - 1] 1;
}else{dp[i][j]max(dp[i-1][j],dp[i][j-1]);
}dp数组如何初始化如果两个数组都没重复最小值就是0数组都初始化成0。确定遍历顺序从前向后遍历。打印dp数组。
class Solution {
public:int longestCommonSubsequence(string text1, string text2) {vectorvectorint dp(text1.size() 1,vectorint(text2.size() 1, 0));int max_dp 0;for (int i 1; i text1.size(); i) {for (int j 1; j text2.size(); j) {if (text1[i - 1] text2[j - 1]) {dp[i][j] dp[i - 1][j - 1] 1;}else{dp[i][j]max(dp[i-1][j],dp[i][j-1]);}max_dp max(max_dp,dp[i][j]);}}return max_dp;}
};1035.不相交的线
题目链接1035.不相交的线
确定dp数组以及下标的含义dp[i][j] 以下标i - 1为结尾的nums1和以下标j - 1为结尾的nums2最长重复子数组长度为dp[i][j]确定递推公式 当nums1[i - 1] 和nums2[j - 1]相等的时候dp[i][j] dp[i - 1][j - 1] 1; 那就看看nums1[i - 2]与nums2[j - 1]的最长公共子序列 和 nums1[ i - 1]与nums2[j - 2]的最长公共子序列取最大的。dp[i][j] max(dp[i - 1][j], dp[i][j - 1]);if (text1[i - 1] text2[j - 1]) {dp[i][j] dp[i - 1][j - 1] 1;
}else{dp[i][j]max(dp[i-1][j],dp[i][j-1]);
}dp数组如何初始化如果两个数组都没重复最小值就是0数组都初始化成0。确定遍历顺序从前向后遍历。打印dp数组。
class Solution {
public:int maxUncrossedLines(vectorint nums1, vectorint nums2) {vectorvectorint dp(nums1.size() 1,vectorint(nums2.size() 1, 0));int max_dp 0;for (int i 1; i nums1.size(); i) {for (int j 1; j nums2.size(); j) {if (nums1[i - 1] nums2[j - 1]) {dp[i][j] dp[i - 1][j - 1] 1;}else{dp[i][j]max(dp[i-1][j],dp[i][j-1]);}max_dp max(max_dp,dp[i][j]);}}return max_dp;}
};53. 最大子序和
题目链接53. 最大子序和
class Solution {
public:int maxSubArray(vectorint nums) {vectorintdp(nums.size(),0);int dp_max INT_MIN;dp[0]nums[0];for(int i 1;inums.size();i){dp[i] max(nums[i],dp[i-1]nums[i]);dp_max max(dp[i],dp_max);}return max(dp[0],dp_max);}
};392.判断子序列
题目链接392.判断子序列
确定dp数组以及下标的含义dp[i][j] 以下标i - 1为结尾的t和以下标j - 1为结尾的s最长重复子数组长度为dp[i][j]当max_dps.size(),s就是t的子序列确定递推公式 当t[i - 1] 和s[j - 1]相等的时候dp[i][j] dp[i - 1][j - 1] 1; 那就看看t[i - 2]与s[j - 1]的最长公共子序列 和 t[ i - 1]与s[j - 2]的最长公共子序列取最大的。dp[i][j] max(dp[i - 1][j], dp[i][j - 1]);if (t[i - 1] s[j - 1]) {dp[i][j] dp[i - 1][j - 1] 1;
}else{dp[i][j]max(dp[i-1][j],dp[i][j-1]);
}dp数组如何初始化如果两个数组都没重复最小值就是0数组都初始化成0。确定遍历顺序从前向后遍历。打印dp数组。
class Solution {
public:bool isSubsequence(string s, string t) {vectorvectorint dp(s.size() 1,vectorint(t.size() 1, 0));int max_dp 0;for (int i 1; i s.size(); i) {for (int j 1; j t.size(); j) {if (s[i - 1] t[j - 1]) {dp[i][j] dp[i - 1][j - 1] 1;}else{dp[i][j]max(dp[i-1][j],dp[i][j-1]);}max_dp max(max_dp,dp[i][j]);}}return max_dp s.size();}
};
