题目1：300 最长递增子序列
题目链接：最长递增子序列
对题目的理解
找出整数数组中最长严格递增子序列的长度
动态规划
动规五部曲
1）dp数组及下标i的含义
dp[i]：以nums[i]为结尾的最长递增子序列的长度
递增比较的时候，如果比较 nums[j] 和 nums[i] 的大小，那么两个递增子序列一定分别以nums[j]为结尾 和 nums[i]为结尾
2）递推公式
3）dp数组初始化
根据dp数组定义，dp[i]至少长度是1，最少包含nums[i] ，dp[i]的最大值不一定是在dp[nums.size()-1]，可能出现在各个位置，因此需要遍历一遍
4）遍历顺序
求递增子序列，dp[i]依赖于前面的元素与当前数值进行比较的结果更新dp[i]的值，i从小到大遍历
for(i=1;i<nums.size();i++) 注意i从1开始，因为dp[0]代表以第一个元素结尾，最长递增子序列的长度就是1
for(j=0;j<i;j++)//j用于遍历从0到j的所有元素，j从小到大遍历，从大到小遍历均可,只要把0~i内的元素全部遍历了就行
5）打印dp数组
代码
class Solution {
public:
int lengthOfLIS(vector<int>& nums) {
//定义并初始化dp数组
vector<int> dp(nums.size(),1);
int result = 1;
//递推
for(int i=1;i<nums.size();i++){
for(int j=0;j<i;j++){
if(nums[i]>nums[j]) dp[i] = max(dp[j]+1,dp[i]);
}
result = max(result,dp[i]);//以每一个元素结尾的长度都遍历一遍，求长度的最大值
}
return result;
}
};- 时间复杂度: O(n^2)
- 空间复杂度: O(n)
题目2：674 最长连续递增序列
题目链接：最长连续递增序列
对题目的理解
整数数组未经排序，找到数组中最长且连续递增的子序列，返回该序列的长度
动态规划
动规五部曲
1）dp数组及下标i的含义
dp[i]:以i结尾的最长连续递增子序列的长度，注意这里只是说了以i结尾，不一定以0开始哟，注意本题的最大长度不一定是在dp[nums.szie()-1],可能出现在各个位置，所以需要遍历一遍求最大值
2）递推公式
不连续递增子序列的跟前0-i 个状态有关，连续递增的子序列只跟前一个状态有关
3）dp数组初始化
至少有1个元素，长度是1 ，dp[i]=1
4）遍历顺序
根据递推公式，i依赖于i-1，所以，从前往后遍历
for(i=1;i<nums.size();i++)， 注意i从1开始
5）打印dp数组
代码
class Solution {
public:
int findLengthOfLCIS(vector<int>& nums) {
//定义并初始化dp数组
vector<int> dp(nums.size(),1);
int result = 1;
for(int i=1;i<nums.size();i++){
if(nums[i]>nums[i-1]) dp[i]=dp[i-1]+1;
result = max(result,dp[i]);
}
return result;
}
};- 时间复杂度：O(n)
- 空间复杂度：O(n)
贪心算法
class Solution {
public:
int findLengthOfLCIS(vector<int>& nums) {
int count=1;
int result = 1;
for(int i=1;i<nums.size();i++){
if(nums[i]>nums[i-1]) count++;//连续递增，count++
else count = 1;//不连续递增，count从1开始计算
result = max(result,count);
}
return result;
}
};- 时间复杂度：O(n)
- 空间复杂度：O(1)
题目3：718 最长重复子数组
题目链接：最长重复子数组
对题目的理解
返回两个整数数组中公共的且长度最长的子数组长度（子数组就是连续子序列）
动态规划
动规五部曲
1）dp数组及下标i的含义
使用二维dp数组表示两个数组的所有比较情况，
dp[i][j]:以i-1为结尾的nums1和以j-1为结尾的nums2的最长重复子数组的长度
注意：本题的最大长度不一定在dp[nums1.size()-1][nums2.size()-1]，可能出现在各个位置，所以需要再遍历一遍，求最大值
2）递推公式
根据递推公式的定义，dp[i][j]的状态只能由dp[i-1][j-1]推导出来，if(nums1[i-1]==nums2[j-1]) dp[i][j]=dp[i-1][j-1]+1 两个数组同时回退所以只能是dp[i-1][j-1]+1，不能是dp[i][j-1]也不能是dp[i-1][j]
3）dp数组初始化
根据dp数组定义（以i-1结尾，以j-1结尾），dp[i][0]无意义状态 0-1无意义；同理，dp[0][j]无意义状态 0-1无意义，为了方便递推公式，将二者初始化为0，最长子数组长度应该从0往上加；
其他的下标的dp值初始化为任意值均可（因为计算递推公式之后会被覆盖），为了代码简洁，将dp全初始化为0
4）遍历顺序
先遍历两个数组中的哪一个都可以
for(i=1;i<=nums1.size();i++){
for(j=1;j<=nums2.size();j++)}
注意从1开始遍历（根据递推公式），且条件是小于等于，因为dp数组的定义是[i][j]代表以i-1，j-1为结尾，只有等于，才能遍历到数组中的最后一个元素，nums1.size()-1,nums2.size()-1
题目要求长度最长的子数组的长度。所以在遍历的时候顺便把dp[i][j]的最大值记录下来。
5）打印dp数组
代码
class Solution {
public:
int findLength(vector<int>& nums1, vector<int>& nums2) {
//定义并从初始化dp数组
vector<vector<int>> dp(nums1.size()+1,vector<int>(nums2.size()+1));
for(int i=0;i<nums1.size();i++){
dp[i][0]=0;
}
for(int j=0;j<nums2.size();j++){
dp[0][j]=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;
result = max(result,dp[i][j]);
}
}
return result;
}
};初始化简便一些
class Solution {
public:
int findLength(vector<int>& nums1, vector<int>& nums2) {
//定义并从初始化dp数组
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;
result = max(result,dp[i][j]);
}
}
return result;
}
};- 时间复杂度：O(n × m)，n 为A长度，m为B长度
- 空间复杂度：O(n × m)
若将dp[i][j]数组定义为nums1以i结尾和nums2以j结尾，那么 第一行和第一列毕竟要进行初始化，如果nums1[i] 与 nums2[0] 相同的话，对应的 dp[i][0]就要初始为1， 因为此时最长重复子数组为1。 nums2[j] 与 nums1[0]相同的话,也是同样要把dp[0][j]初始化为1,如下图
代码
class Solution {
public:
int findLength(vector<int>& nums1, vector<int>& nums2) {
//定义并从初始化dp数组
vector<vector<int>> dp(nums1.size(),vector<int>(nums2.size(),0));
for(int i=0;i<nums1.size();i++) if(nums1[i]==nums2[0]) dp[i][0]=1;
for(int j=0;j<nums2.size();j++) if(nums2[j]==nums1[0]) dp[0][j]=1;
int result = 0;
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;
result = max(result,dp[i][j]);
}
}
return result;
}
};上述代码会出现如下的错误
错误的原因是即使是上面的初始化更新了dp数组，dp数组中是1，但是最终返回了result，而result又是在for循环中，两个for循环都是从1开始记录，所以整个for循环并不包括初始化的那一列，那一行进行比较，所以最终返回的结果是0
将代码更改为如下：i=0与j=0，初始化的这一行和一列还是要在for循环中进行比较的
class Solution {
public:
int findLength(vector<int>& nums1, vector<int>& nums2) {
//定义并从初始化dp数组
vector<vector<int>> dp(nums1.size(),vector<int>(nums2.size(),0));
for(int i=0;i<nums1.size();i++) if(nums1[i]==nums2[0]) dp[i][0]=1;
for(int j=0;j<nums2.size();j++) if(nums2[j]==nums1[0]) dp[0][j]=1;
int result = 0;
for(int i=0;i<nums1.size();i++){
for(int j=0;j<nums2.size();j++){
if(nums1[i]==nums2[j] && i>0 && j>0) dp[i][j]=dp[i-1][j-1]+1;
result = max(result,dp[i][j]);
}
}
return result;
}
};
