教育培训类网站开发,安徽智能网站建设制作,体育用品网站模板,哪些公司需要网站开发工程师300.最长递增子序列 这道题还挺简单的#xff0c;咱们设置dp[i]表示到第i个数字时的递增子序列的最长的值#xff0c;那么dp[i]就要遍历从0到i-1的数#xff0c;也就是看看当前这个数字是否比前面的数字大#xff0c;如果大的话就看看现在的子序列长度是否会长于前面那个数…300.最长递增子序列 这道题还挺简单的咱们设置dp[i]表示到第i个数字时的递增子序列的最长的值那么dp[i]就要遍历从0到i-1的数也就是看看当前这个数字是否比前面的数字大如果大的话就看看现在的子序列长度是否会长于前面那个数字代表的子序列长度11是表示加上当前这个数字如果不会的话就更新最长值。
https://leetcode.cn/problems/longest-increasing-subsequence/submissions/510789123/
class Solution {
public:int lengthOfLIS(vectorint nums) {vectorintdp(nums.size(),1);for(int i1;idp.size();i){for(int j0;ji;j){if(nums[i]nums[j]){dp[i]max(dp[i],dp[j]1);}}}int result0;for(int i0;inums.size();i){resultmax(dp[i],result);}return result;}
};
674.最长连续递增序列 动规题写多了题感也就来了这道题求最长连续递增序列dp[i]表示到第i个数字的最长递增子序列是多少如果nums[i]nums[i-1],自然说明i可以加入到前面那个序列里面所以dp[i]dp[i-1]如果nums[i]nums[i-1],则说明i不可以加入所以dp[i]还是维持1注意这里就涉及初始化的问题因为根据dp[i]的解释可以知道初始化时最长递增子序列也就是这个数字本身。
https://leetcode.cn/problems/longest-continuous-increasing-subsequence/description/
class Solution {
public:int findLengthOfLCIS(vectorint nums) {vectorintdp(nums.size(),1);for(int i1;inums.size();i){if(nums[i]nums[i-1]){dp[i]dp[i-1];}}int result0;for(int i0;inums.size();i){resultmax(result,dp[i]);}return result;}
};
718.最长重复子数组 这道题我听完讲解的一半就去做但是过不了仔细一看我的判断条件写成dp[i]dp[j],这就要回到这道题的原始了dp[i][j]表示到第一个数组的第i个第二个数组的第j个时候的最长重复子数组这里我们把dp[i][j]初始化的数组增加了最上面【0】下标的一行最左边【0】下标的一列这样我们可以按照直观的表示第i个就是从nums1数第i个而不是从0下标开始就方便我们计算了但是需要注意的就是判断条件要是dp[i-1]dp[j-1]因为虽然数是那样从1开始数但是我们遍历nums1和nums2还是得从下标0的时候开始遍历。
https://leetcode.cn/problems/maximum-length-of-repeated-subarray/description/
class Solution {
public:int findLength(vectorint nums1, vectorint nums2) {vectorvectorintdp(nums1.size()1,vectorint(nums2.size()1,0));int result0;for(int i1;inums1.size();i){for(int j1;jnums2.size();j){if(nums1[i-1]nums2[j-1]){dp[i][j]dp[i-1][j-1]1;resultmax(result,dp[i][j]);}}}return result;}
};
