北京网站设计制作飞沐,安徽建设工程信息网监理查询,做网站用html5,高定网站300.最长递增子序列
题目链接
力扣#xff08;LeetCode#xff09;官网 - 全球极客挚爱的技术成长平台
求解思路
动规五部曲
1.dp数组及其下标定义#xff1a;
dp[i]表示包括i以前的以nums[i]结尾的最长递增子序列的长度
2.状态转移方程#xff1a;
位置i的最长升序…300.最长递增子序列
题目链接
力扣LeetCode官网 - 全球极客挚爱的技术成长平台
求解思路
动规五部曲
1.dp数组及其下标定义
dp[i]表示包括i以前的以nums[i]结尾的最长递增子序列的长度
2.状态转移方程
位置i的最长升序子序列等于j从0到i-1各个位置的最长升序子序列 1 的最大值
所以 if (nums[i] nums[j]) dp[i] max(dp[i], dp[j] 1);
注意要取dp[j] 1的最大值
3.初始化
每一个i对应的dp[i]即最长递增子序列起始大小至少都是1
4.遍历顺序
i 从前向后遍历j 从 0 遍历到 i-1
5.举例推导dp数组
入输入[0,1,0,3,2]dp数组如下 代码
class Solution {
public:int lengthOfLIS(vectorint nums) {int n nums.size();if (n 1) return 1;int result 0;vectorint dp(n,1); // 保底为1for (int i 1; i n; i){for (int j 0; j i; j){if (nums[j] nums[i]){dp[i] max(dp[i], dp[j] 1);}}result max(result, dp[i]); // 返回dp[i]的最大值}return result;}
};
674. 最长连续递增序列
题目链接
力扣LeetCode官网 - 全球极客挚爱的技术成长平台
求解思路
相比于前一道题目不需要在用j来遍历0到i-1只需要关注i-1即可
代码
class Solution {
public:int findLengthOfLCIS(vectorint nums) {int n nums.size();if (n 1) return 1;int result 0;vectorint dp(n, 1);for (int i 1; i n; i){if (nums[i-1] nums[i]){dp[i] max(dp[i], dp[i-1]1);}result max(result, dp[i]);}return result;}
};
718. 最长重复子数组
题目链接
力扣LeetCode官网 - 全球极客挚爱的技术成长平台
求解思路
动规五部曲
1.确定dp数组及其下标含义
以下标i-1为结尾的A和以下标j-1位结尾的B最长重复子数组长度为dp[i][j]注意dp[i][j]对应的是i-1结尾的A和j-1结尾的B
2.确定递推公式
dp[i][j]的状态只能由dp[i][j]推导出来仅当A[i-1]和B[j-1]相等的时候dp[i][j] dp[i - 1][j - 1] 1;
3.dp数组的初始化
根据dp[i][j]的定义dp[i][0] 和dp[0][j]其实都是没有意义的但只有dp[0][0]初始为0才符合递推公式的推导
4.确定遍历顺序
外层for循环遍历A内层for循环遍历B
遍历的时候要把dp[i][j]的最大值记录下来
5.举例推导dp数组
示例1中A: [1,2,3,2,1]B: [3,2,1,4,7]为例画一个dp数组的状态变化如下 代码
class Solution {
public:int findLength(vectorint nums1, vectorint nums2) {int n1 nums1.size(), n2 nums2.size();int result 0;vectorvectorint dp(n11,vectorint(n21,0));for (int i 1; i n1; i){for (int j 1; j n2; j){if (nums1[i-1] nums2[j-1]){dp[i][j] dp[i-1][j-1] 1;}result max(result, dp[i][j]);}}return result;}
};
