300 最长递增子序列
思路：在初始化时，将每个元素的初始值设为1，因为单个元素也是一个上升子序列。
接下来，从第2个元素开始，遍历数组，对于每个元素nums[i]，再次遍历该元素前面的所有元素nums[j]，如果nums[i]大于nums[j]，那么更新dp[i]的值为max(dp[i], dp[j]+1)。这是因为如果nums[i]可以接在nums[j]后面形成一个更长的上升子序列，那么dp[i]的值应该等于dp[j]+1。
最后，遍历整个dp数组，返回其中最大的值，即为最长上升子序列的长度。
1.动态规划
class Solution {
public:
int lengthOfLIS(vector<int>& nums) {
if(nums.size() <= 1) return nums.size();
vector<int> dp(nums.size(), 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 最长连续递增序列
思路：
首先判断输入数组是否为空，如果为空，直接返回0。
定义一个变量result记录历史最长长度，初始化为1。
定义一个长度为n的dp数组，dp[i]表示以nums[i]结尾的最长连续递增子序列的长度，初始化为1。
从第二个元素开始遍历nums数组，如果当前元素大于前一个元素，则当前连续递增子序列长度加1，否则重置为1。
每次更新result为历史最长长度和当前最长长度中的较大值。
最后返回result即可。
1.动态规划
class Solution {
public:
int findLengthOfLCIS(vector<int>& nums) {
if(nums.size() == 0) return 0;
int result = 1;
vector<int> dp(nums.size(), 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 最长重复子数组
思路：
定义一个二维数组 dp，其中 dp[i][j] 表示以 nums1[i-1] 和 nums2[j-1] 结尾的最长公共子序列长度。然后，我们可以根据 nums1[i-1] 和 nums2[j-1] 是否相等分两种情况讨论：
如果 nums1[i-1] 和 nums2[j-1] 相等，则说明这两个数可以加入到最长公共子序列中，因此 dp[i][j] = dp[i-1][j-1] + 1。
如果 nums1[i-1] 和 nums2[j-1] 不相等，则说明这两个数不能同时加入到最长公共子序列中，因此最长公共子序列不包括这两个数，所以此时 dp[i][j] = 0。
最后，我们需要遍历整个 dp 数组，找到其中的最大值即为所求的最长公共子序列长度。
1.动态规划
class Solution {
public:
int findLength(vector<int>& nums1, vector<int>& nums2) {
vector<vector<int>> dp(nums1.size() + 1, vector<int> (nums2.size() + 1, 0));
int result = 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] > result) result = dp[i][j];
}
}
return result;
}
};
