题目1 1143 最长公共子序列
题目链接 1143 最长公共子序列
题意
返回两个字符串text1和text2的最长公共子序列的长度 若不存在，则返回0
子序列是指原字符相对顺序不改变
动态规划
动规五部曲
1）dp数组及下标i的含义
dp[i][j] 表示以[0，i-1]的text1，[0，j-1]的text2的公共子序列的最长长度
2）dp数组初始化
根据递推公式 dp[i][0]表示text1字符串与空字符串的公共子序列的长度最长是0 dp[i][0] = 0
dp[0][j]表示空字符串与text2字符串的公共子序列的长度最长是0 dp[0][j] = 0
其他下标处的dp[i][j]可以初始化为任意值 因为可以由递推公式求得
3）递推公式
if(text[i-1] == text[j-1]) dp[i][j] = dp[i-1][j-1] + 1;
else dp[i][j] = max(dp[i][j-1], dp[i-1][j])；
如果不相同的话，考虑两种情况取最大者
1）text1字符串与text2字符串在当前位置的前一个位置进行比较 dp[i][j-1]
2）text2字符串与text1字符串在当前位置的前一个位置进行比较 dp[i-1][j]
4）遍历顺序
根据递推公式，从左到右遍历，从上到下遍历
for(int i = 1; i < text1.size(); i++){
for(int j = 1; j < text2.size(); j++)}
5）打印dp数组
代码
class Solution {
public:
int longestCommonSubsequence(string text1, string text2) {
//定义并初始化dp数组
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]);
// cout <<"i = "<< i << " " << "j = " << j << " " << "dp" << dp[i][j] << endl;
}
}
return dp[text1.size()][text2.size()];
}
};- 时间复杂度: O(n * m)，其中 n 和 m 分别为 text1 和 text2 的长度
- 空间复杂度: O(n * m)
题目2 1035 不相交的线
题目链接 ：1035 不相交的线
题意
整数数组nums1和nums2中，满足nums1[i] == nums2[j]时，使用直线连接两个数字 。
绘制的直线不与其他连线相交 说明在数组nums1中 找到一个与nums2相同的子序列，只要这个子序列不改变相对顺序，那么连线就不会相交
因此最大连线数就是最长公共子序列的长度 和上题题解一样
代码
class Solution {
public:
int maxUncrossedLines(vector<int>& nums1, vector<int>& nums2) {
//定义并初始化dp数组
vector<vector<int>> dp(nums1.size() + 1, vector<int>(nums2.size() + 1, 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]);
}
}
}
return dp[nums1.size()][nums2.size()];
}
};- 时间复杂度: O(n * m)
- 空间复杂度: O(n * m)
题目3 53 最大子数组和
题目链接 53 最大子数组和
题意
返回整数数组nums中的连续子数组（至少包含一个元素）的最大和
即 找到连续子序列中和最大的那个
动态规划
动规五部曲
1）dp数组及下标i的含义
dp[i] 表示以nums[i]为结尾的连续数组的最大和
2）dp数组初始化
根据递推公式 dp[0] = nums[0]; 其它dp[i]初始化为0
3）递推公式
分两种情况 取最大者
1）延续前面的和 dp[i-1] + nums[i]
2）以当前位置为起点，重新开始 nums[i]
dp[i] = max(dp[i-1]+nums[i]，nums[i])
4）遍历顺序
根据递推公式 从前向后遍历 for(int i = 1; i<nums.size(); i++)
注意，最终的最大和不一定包含最后一个元素，所以需要遍历dp数组，找到最大值
5）打印dp数组
代码
class Solution {
public:
int maxSubArray(vector<int>& nums) {
//定义dp数组 初始化
vector<int> dp(nums.size(), 0);
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]);
result = max(result, dp[i]);
}
return result;
}
};- 时间复杂度：O(n)
- 空间复杂度：O(n)
