本文主要是介绍LeetCode 第51天 | 300. 最长递增子序列 674. 最长连续递增序列 718. 最长重复子数组 动态规划，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
300. 最长递增子序列
用当前值与之前的左右值比较，如果大于前面的值，那么就可以用前面的dp加上长度一（当前值本身长度）。就是前面的值大小记录下来，后面会用的到，到dp[i]的点记录了dp[i]之前的局部最长子序列，那么如果后续遍历到的值严格大于该值的话，就可以动态更新后面的值了。解决局部问题记录状态，解决全局问题就可以利用局部解的值来优化全局解。
class Solution {
public:int lengthOfLIS(vector<int>& nums) {// dp[i]表示到i的最长递增子序列if (nums.size() == 0) return 0;vector<int> dp(nums.size(), 1);int res = 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[i], dp[j]+1);}}if (dp[i] > res) res = dp[i];}return res;}
};
674. 最长连续递增序列
这个序列要求是连续的，相当于子串。
在一个循环遍历中如果nums[i] > nums[i-1]，那么就证明该值和前面一个还是递增的，而前面一个连续多少个，这已经在前面计算过了。至于更前面相隔不连续的序列，就不用了考虑了。同时利用res记录当前的最大值，即为最终结果。
class Solution {
public:int findLengthOfLCIS(vector<int>& nums) {int n = nums.size();if (n == 0) return 0;int res = 1;vector<int> dp(n, 1);for (int i = 1; i < n; i++) {if (nums[i] > nums[i-1])dp[i] = dp[i-1] + 1;if (dp[i] > res) res = dp[i];}for (auto i : dp) cout<<i<<" ";return res;}
};
718. 最长重复子数组
找两个数组的重复子数组，子数组的连续的，相当于子串。这题其实我还没搞透彻，这是跟着代码随想录敲的代码。下次一定搞懂（嘻嘻）
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 res = 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] > res) res = dp[i][j];}}return res;}
};
今天已经写了十题左右的LeetCode了，一般是自己写，一半是照抄的，当然照抄并不可耻，熟能生巧，起码也熟练度上有进步的。今天最难的题是含有冻结期的股票交易，状态难想，代码不规整，挺难实现的，但是得明确一个原则就是股票求的是最佳受益，dp[i]表示第i天的受益，至于第二维的状态定义完全取决于自己。子序列是最清新的题，就是再用一个空间来存储到达这里的最长递增序列，之后遍历时就可以利用前面局部已经得到的结果。加油，一天有一天的收获。
这篇关于LeetCode 第51天 | 300. 最长递增子序列 674. 最长连续递增序列 718. 最长重复子数组 动态规划的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
