代码随想录算法训练营day43|动态规划part10
今天的是子序列问题，第二题难度不大，可以采用类似贪心的思路求解。第一题的思想比较新颖，注意dp[i]是以i为末尾元素的最长递增子序列，可以用两层循环，第二层循环遍历从0到i-1，通过不断更新dp[i]的值求解最长递增子序列，这里的思路很巧妙。
另外，第一题还可以用贪心的方法，要使子序列尽可能长，就要使每个子序列中的数尽可能小，若遇到更小的数就将其替换。可以写出如下代码：
for(auto num:nums){
auto it=ranges::lower_bound(res,num);
if(it==res.end()) {
res.push_back(num);
}
else *it=num;
}
return res.size();第三题的思路和第一题类似，
vector<vector<int>>dp(nums1.size(),vector<int>(nums2.size(),0));
//dp[i][j]表示以nums1[i],nums2[j]为末尾元素的最长子序列的长度，需要初始化为0 if(nums1[i]==nums2[j]&&i>0&&j>0) dp[i][j]=dp[i-1][j-1]+1;这行代码的意思是如果两个数列有数字相同，就在前面的基础上加1，因为两个数列是同步的。
这道题卡哥采用的是i-1,j-1的写法，我认为用i，j更容易理解，只是需要多一步初始化的过程同时要防止数组越界：
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;先处理完第一行，再处理后面的。