哈尔滨服务专业的建站,外链seo招聘,招商网站建设定做,天津免费做网站300.最长递增子序列 题目链接/文章讲解/视频讲解#xff1a;代码随想录 1.代码展示
//300.最长递增子序列
int lengthOfLIS(vectorint nums) {if (nums.size() 1) {return 1;}//step1 构建dp数组//dp[i]的含义是长度未nums数组中长度为i 1的数组的最长子序列长…300.最长递增子序列 题目链接/文章讲解/视频讲解代码随想录 1.代码展示
//300.最长递增子序列
int lengthOfLIS(vectorint nums) {if (nums.size() 1) {return 1;}//step1 构建dp数组//dp[i]的含义是长度未nums数组中长度为i 1的数组的最长子序列长度vectorint dp(nums.size(), 1);//step2 状态转移方程//将第i 1个数和前面的i个数一一对比找到最大的dp[i]//if (nums[i] nums[j]) dp[i] max(dp[i], dp[j] 1);//step3 初始化//step4 开始遍历int nResult 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);}}nResult max(nResult, dp[i]);}return nResult;
} 2.本体小节 思考明确本题dp数组含义dp[i]指的是到下标为i的数组中最长递增子序列个数遍历nums数组再对下标i前的所有数字进行遍历通过比较nums[i]和nums[j]的大小来更新最大dp[i]即dp[i] max(dp[i], dp[j] 1)i下次遍历之前更新result即可最终取出最大的dp[i]作为结果注意初始化时每个元素都为1因为元素本身递增子序列就为1。 基本思路如上注意初始化和状态转移方程。
674. 最长连续递增序列 题目链接/文章讲解/视频讲解代码随想录 1.代码展示
//674.连续最长递增子序列
int findLengthOfLCIS(vectorint nums) {if (nums.size() 1) {return 1;}vectorint dp(nums.size(), 1);int nResult 0;for (int i 1; i nums.size(); i) {if (nums[i] nums[i - 1]) {dp[i] dp[i - 1] 1;}nResult max(nResult, dp[i]);}return nResult;
} 2.本题小节 思考本题和上一题最大的不同在于遍历时当前值只需要和前一个值进行比较即可不需要对当前值之前的所有值进行遍历因此dp[i]只与dp[i - 1]有关如果nums[i] nums[i - 1]那么dp[i] dp[i - 1] 1并更新result获得最大的dp[i]初始化时dp均为1。 基本思路如上注意初始化和状态转移方程。
718. 最长重复子数组 题目链接/文章讲解/视频讲解代码随想录 1.代码展示
//718.最长重复子数组
int findLength(vectorint nums1, vectorint nums2) {vectorvectorint dp(nums1.size() 1, vectorint(nums2.size() 1, 0));int nResult 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;nResult max(nResult, dp[i][j]);}}}return nResult;
}
2.本题小节 思考本题和上面两题不同的是本题要比较的是两个数组的最长重复子数组。构建dp数组dp[i][j]含义是以下标为 i - 1 和 j - 1 为结尾的数组A和B的最长重复子序列初始化时数组全部初始化为0这里dp[i][j]的含义就体现了出来不需要对dp[0][j]和dp[i][0]一个一个初始化。首先对nums1开始遍历再对nums2遍历都从1开始当nums1[i - 1] nums2[j - 1]时此时触发状态转移方程dp[i][j] dp[i - 1][j - 1] 1并更新result。 基本思路注意本题使用的是二维数组并把每种情况都列举了出来。
