您现在的位置是:首页 >其他 >代码随想录Day52 | 1143.最长公共子序列 、1035.不相交的线 、53. 最大子序和 动态规划网站首页其他
代码随想录Day52 | 1143.最长公共子序列 、1035.不相交的线 、53. 最大子序和 动态规划
简介代码随想录Day52 | 1143.最长公共子序列 、1035.不相交的线 、53. 最大子序和 动态规划
1143.最长公共子序列
dp含义:dp[i][j] 以[0,i-1]nums1和[0,j-1]nums2的最长公共子序列的长
递推公式:dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
初始化:dp[i][0]=0,dp[0][j]=0
遍历顺序:i,j从1开始
class Solution {
public:
int longestCommonSubsequence(string text1, string text2) {
vector<vector<int>> dp(text1.size() + 1, vector<int>(text2.size() + 1, 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]);
}
}
}
return dp[text1.size()][text2.size()];
}
};
1035.不相交的线
和上一题一样,只是换一个形式
class Solution {
public:
int maxUncrossedLines(vector<int>& A, vector<int>& B) {
vector<vector<int>> dp(A.size() + 1, vector<int>(B.size() + 1, 0));
for (int i = 1; i <= A.size(); i++) {
for (int j = 1; j <= B.size(); j++) {
if (A[i - 1] == B[j - 1]) {
dp[i][j] = dp[i - 1][j - 1] + 1;
} else {
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
}
}
}
return dp[A.size()][B.size()];
}
};
53. 最大子序和 动态规划
dp[i]:以i为尾(nums[i])的最大连续子序列的和
递推公式:dp[i]=max(dp[i-1]+nums[i],nums[i])
初始化:dp[0]=nums[0]
遍历顺序:从前往后遍历
class Solution {
public:
int maxSubArray(vector<int>& nums) {
if (nums.size() == 0) return 0;
vector<int> dp(nums.size());
dp[0] = nums[0];
int result = dp[0];
for (int i = 1; i < nums.size(); i++) {
dp[i] = max(dp[i - 1] + nums[i], nums[i]);
if (dp[i] > result) result = dp[i];
}
return result;
}
};
风语者!平时喜欢研究各种技术,目前在从事后端开发工作,热爱生活、热爱工作。