最长递增子序列问题
问题理解
返回给定整数数组中最长严格递增子序列的长度。
思路
原始：在左域找到最小，在右边找最小比它大的，更新左域，在右边找最小比它大的。
如果用动态规划的思路:当前状态与上一个状态的关系来看，当前状态可以是两种状态：
(1)保留：
比其前一个元素大；
(2)不保留：
比其前一个元素小。
初始化：初始化为第一个元素；
想不下去了，看题解。
题解思路
（1）DP数组：DP数组表示长度为i+1的整数数组中所能得到的最长递增子序列的长度。
不懂为何强调要以nums[i]结尾；其实没必要
（2）递推公式：
递推公式的目标就是要更新序列长度，依据就是原始思路中元素大小的比较。
（3）初始化
在序列长度不为0的情况下，最大递增子序列至少为1.
if（nums.size()<=1) return nums.size();
vector <int> dp(nums.size(),1)
(4) 遍历顺序：从前到后
（5）数组举例推导：
[0，1，0，3，2]
dp数组：[1,2,2,3,3]
代码实现
#include<iostream>
#include<vector>
using namespace std;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=1;i<nums.size();i++){for(int j=0;j<i;j++){if(nums[i]>nums[j]) dp[i]=max(dp[i],dp[j]+1);}cout<<dp[i]<<endl;if(dp[i]>result) result=dp[i]; } return result; }
};
int main(){Solution sol;vector<int> nums;nums={0,1,0};cout<<sol.lengthOfLIS(nums)<<endl;return 0;
}
小结
我的原始思路存在两个问题：首先没有明确DP数组的具体含义，需要明确DP数组已经是一个长度了，已经是我们要的结果，而我的原始思路停留在元素的处理上。在一维数组中通过相邻元素大小的比较实现序列增加，如此处理构建长度和序列的桥梁。
第二个关键点是DP数组并不是最终的结果，即图中所示，通过对result的更新来取得最大长度。具体体现为：在序列{0,1,0}中，dp数组[1,2,1],通过result记录了2.
最长连续递增序列
问题理解
给定整数数组，找到最长且连续递增的子序列，返回其长度。
思路
乍看这道题目和上一个最长严格递增子序列没差。但是看示例{1，3，5，4，7}的最长连续递增序列是[1,3,5]而非[1,3,5,7]就可以明确，不光要求子序列是连续递增，并且要求在原数组中子序列元素之间也是连续递增。
具体实现
class Solution {
public:int findLengthOfLCIS(vector<int>& nums) {if (nums.size() <= 1)return nums.size();vector<int> dp(nums.size(), 1);int result = 0;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;}
};
更加顺畅的贪心思路：
class Solution {
public:int findLengthOfLCIS(vector<int>& nums) {if (nums.size() <= 1)return nums.size();int count = 1;int result = 0;for (int i = 1; i < nums.size(); i++) {if (nums[i] > nums[i - 1])count++;else {count = 1;}if (count > result)result = count;}return result;}
};
最长重复子数组
题目理解
求给定两数组中最长公共子数组的长度。题目中没有明确子数组是否需要在原数组中连续？{3，6，5，4}与{3，5，4}，暂且认为子数组的元素在两个数组中是相邻出现的。
思路
原始思路：找到第一个相同的元素，然后开始挪，挪到不同的元素，停下。记录一下长度，比前面挪得长，更新。
动态规划思路：DP数组记录公共子数组的长度；
递推公式：dp[i][j]=dp[i-1][j-1]+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; }
};