300. 最长递增子序列
视频讲解
主要思路:
(1)dp[ i ]:以num[ i ]为结尾的最长递增子序列长度
(2)初始化:全部初始化为1,因为最短递增子序列(就包含自己)长度也应该是1
(3)递推公式:第一层循环从前往后遍历,第二层循环遍历第一层循环里这一段每个数字与num[ i ] 大小,如果这个数字小于num[ i ],说明保持递增,则dp[ i ]取原来值与dp[ j ] + 1里面最大值
(4)遍历顺序:包含在前面递推公式里了
代码实现:
class Solution {
public:
int lengthOfLIS(vector<int>& nums) {
int len = nums.size();
vector<int> dp(len, 1);
int result = 0;
for(int i = 0; i < nums.size(); i++) {
for(int j = 0; j <= i; j++) {
if(nums[i] > nums[j]) {
dp[i] = max(dp[i], dp[j] + 1);
}
}
if(dp[i] > result) {
result = dp[i];
}
}
return result;
}
};
674. 最长连续递增序列
主要思路:
相对于上一题就是要求连续,那递推公式只用一层for循环就行,只要当前比上一个大就递增1
代码实现:
class Solution {
public:
int findLengthOfLCIS(vector<int>& nums) {
int len = nums.size();
vector<int> dp(len, 1);
int result = 1;
for(int i = 1; i < nums.size(); i++) {
if(nums[i] > nums[i - 1]) {
dp[i] = dp[i - 1] + 1;
}
if(dp[i] > result) {
result = dp[i];
}
}
return result;
}
};
718. 最长重复子数组
视频讲解
主要思路:
(1)dp[ i ] [ j ]:以i - 1结尾nums1与以j - 1结尾nums2的最长重复子数组长度,之所以要设置为减1是为了便于初始化
(2)初始化:均初始化为0
(3)递推公式:注意dp数组定义,所以比较的是nums[ i - 1]与nums[ j - 1]如果相等,则dp[ i ][ j ] = dp[ i - 1][ j - 1] + 1
(4)遍历顺序:注意本题从1开始遍历,一直遍历到下标等于两个数组长度的位置,因为由定义减1,只有这样才能保证把数组遍历完
代码实现:
class Solution {
public:
int findLength(vector<int>& nums1, vector<int>& nums2) {
int row = nums1.size() + 1;
int col = nums2.size() + 1;
int ret = 0;
vector<vector<int>> dp(row, vector<int>(col, 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;
}
if(dp[i][j] > ret) {
ret = dp[i][j];
}
}
}
return ret;
}
};