参考
题目一：LeetCode 1143.最长公共子序列
-
确定dp数组下标及其含义
dp[i][j]：字符串text1中的0～i字符构成的字符串和字符串text2中的0～j字符构成的字符串的最长 公共子序列 的长度为dp[i][j]。注意和之前做过的LeetCode 718. 最长重复子数组中dp数组定义的区别！！ -
确定递推公式
if(text1[i] == text2[j])
dp[i][j] = dp[i-1][j-1] + 1;
else
dp[i][j] = max(dp[i-1][j],dp[i][j-1]);
- 初始化dp数组
需要初始化dp数组的第0行和第0列，代码如下：
vector<vector<int>> dp(text1.size(),vector<int>(text2.size(),1));
for(int i = 0; i < text1.size(); i++){
if(text1[i] != text2[0]) dp[i][0] = 0;
else break;
}
for(int j = 0; j < text2.size(); j++){
if(text2[j] != text1[0]) dp[0][j] = 0;
else break;
}
4.确定遍历顺序
两层for循环，里层和外层都是一样的，每层循环从前往后遍历。
- 举例推导dp数组
完整的代码实现如下：
class Solution {
public:
int longestCommonSubsequence(string text1, string text2) {
vector<vector<int>> dp(text1.size(),vector<int>(text2.size(),1));
for(int i = 0; i < text1.size(); i++){
if(text1[i] != text2[0]) dp[i][0] = 0;
else break;
}
for(int j = 0; j < text2.size(); j++){
if(text2[j] != text1[0]) dp[0][j] = 0;
else break;
}
for(int i = 1; i < text1.size(); i++){
for(int j = 1; j < text2.size(); j++){
if(text1[i] == text2[j])
dp[i][j] = dp[i-1][j-1] + 1;
else
dp[i][j] = max(dp[i-1][j],dp[i][j-1]);
}
}
return dp.back()[text2.size()-1];
}
};
题目二：LeetCode 1035.不相交的线
这个题和上个题一模一样，没有区别，关键想明白怎么个一样法。
class Solution {
public:
int maxUncrossedLines(vector<int>& nums1, vector<int>& nums2) {
vector<vector<int>> dp(nums1.size(),vector<int>(nums2.size(),1));
for(int i = 0; i < nums1.size(); i++){
if(nums1[i] != nums2[0]) dp[i][0] = 0;
else break;
}
for(int j = 0; j < nums2.size(); j++){
if(nums2[j] != nums1[0]) dp[0][j] = 0;
else break;
}
for(int i = 1; i < nums1.size(); i++){
for(int j = 1; j < nums2.size(); j++){
if(nums1[i] == nums2[j])
dp[i][j] = dp[i-1][j-1] + 1;
else
dp[i][j] = max(dp[i-1][j],dp[i][j-1]);
}
}
return dp.back()[nums2.size()-1];
}
};
题目三：LeetCode 53. 最大子序和
-
确定dp数组及其下标的含义
dp[i]：第i个元素位置处连续子数组的最大和，dp[i]表示的局部最大。 -
确定递推公式
因为dp[i]表示的局部最大，因此dp[i]有两个可能：
- dp[i-1] + nums[i]，即在上一个累加值的基础上，继续累加
- nums[i]，放弃之前的累加值（累加值变小的情况），重新开始累加
最终要取最大值，dp[i] = max(dp[i-1]+nums[i],nums[i])。
- 初始化dp数组
int result = nums[0];
dp[0] = nums[0];
-
确定遍历顺序
根据递推关系，要从前往后遍历。 -
举例推导dp数组
完整的代码实现如下：
class Solution {
public:
int maxSubArray(vector<int>& nums) {
vector<int> dp(nums.size());
int result = nums[0];
dp[0] = nums[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;
}
};