做一套公司网站费用,外贸生意如何做,wordpress 链接小图标,表白网站源码大全文档讲解#xff1a;最长递增子序列 最长连续递增序列 最长重复子数组 300.最长递增子序列
题目链接#xff1a;https://leetcode.cn/problems/longest-increasing-subsequence/description/
思路#xff1a; 设dp[i]表示i之前包括i的以nums[i]结尾的最长递增子序列的长… 文档讲解最长递增子序列 最长连续递增序列 最长重复子数组 300.最长递增子序列
题目链接https://leetcode.cn/problems/longest-increasing-subsequence/description/
思路 设dp[i]表示i之前包括i的以nums[i]结尾的最长递增子序列的长度。 位置i的最长升序子序列等于j从0到i-1各个位置的最长升序子序列 1 的最大值。 所以if (nums[i] nums[j]) dp[i] max(dp[i], dp[j] 1); 每一个i对应的dp[i]即最长递增子序列起始大小至少都是1。 dp[i] 是有0到i-1各个位置的最长递增子序列 推导而来那么遍历i一定是从前向后遍历。 j其实就是遍历0到i-1那么是从前到后还是从后到前遍历都无所谓只要吧 0 到 i-1 的元素都遍历了就行了。 所以默认习惯 从前向后遍历。
核心代码
class Solution {
public:int lengthOfLIS(vectorint nums) {if (nums.size() 1) return nums.size();vectorint 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);}if (dp[i] result) result dp[i]; // 取长的子序列}return result;}
};
674.最长连续递增序列
题目链接https://leetcode.cn/problems/maximum-length-of-repeated-subarray/description/
思路 设dp[i]以下标i为结尾的连续递增的子序列长度为dp[i]。 如果 nums[i] nums[i - 1]那么以 i 为结尾的连续递增的子序列长度 一定等于 以i - 1为结尾的连续递增的子序列长度 1 。 即dp[i] dp[i - 1] 1; 以下标i为结尾的连续递增的子序列长度最少也应该是1即就是nums[i]这一个元素。 所以dp[i]应该初始1;
核心代码 class Solution {
public:int findLengthOfLCIS(vectorint nums) {if (nums.size() 0) return 0;int result 1;vectorint dp(nums.size() ,1);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;}
}; 718.最长重复子数组
题目链接https://leetcode.cn/problems/longest-continuous-increasing-subsequence/description/
思路 设dp[i][j] 以下标i - 1为结尾的A和以下标j - 1为结尾的B最长重复子数组长度为dp[i][j]。 根据dp[i][j]的定义dp[i][j]的状态只能由dp[i - 1][j - 1]推导出来。 即当A[i - 1] 和B[j - 1]相等的时候dp[i][j] dp[i - 1][j - 1] 1; 根据dp[i][j]的定义dp[i][0] 和dp[0][j]其实都是没有意义的 但dp[i][0] 和dp[0][j]要初始值因为 为了方便递归公式dp[i][j] dp[i - 1][j - 1] 1; 所以dp[i][0] 和dp[0][j]初始化为0。
核心代码
class Solution {
public:int findLength(vectorint nums1, vectorint nums2) {vectorvectorint dp (nums1.size() 1, vectorint(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;}
};
今日总结 这次的题学习时长2h以前做过类似的。 快返校了接着论文idea头大。
