LeetCode300.最长递增子序列
LeetCode300.最长递增子序列
给你一个整数数组 nums ,找到其中最长严格递增子序列的长度。
子序列是由数组派生而来的序列,删除(或不删除)数组中的元素而不改变其余元素的顺序。例如,[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。
示例 1:
- 输入:nums = [10,9,2,5,3,7,101,18]
- 输出:4
- 解释:最长递增子序列是 [2,3,7,101],因此长度为 4 。
示例 2:
- 输入:nums = [0,1,0,3,2,3]
- 输出:4
示例 3:
- 输入:nums = [7,7,7,7,7,7,7]
- 输出:1
提示:
- 1 <= nums.length <= 2500
- -104 <= nums[i] <= 104
动态规划思路讲解
- 我之前也讲过一篇最长上升子序列的文章,也可以去看看,本文基于线性dp:最长上升子序列 - Tomorrowland_D - 博客园 (cnblogs.com))来详细讲解这道题的思路
状态变量以及其含义
- 我们设置状态变量dp[i],表示
以nums[i]为结尾的最长上升子序列的长度
- 我们举个例子,以示例1为例,我们来推导一下为什么可以用
dp[i]
来表示以nums[i]为结尾的最长上升子序列 - nums数组: [10,9,2,5,3,7,101,18]
- 以10结尾的最长上升子序为:[10]
- 以9为结尾的最长上升子序列为:[9]
- 以2为结尾的最长上升子序列为:[2]
- 以5为结尾的最长上升子序列为:[2,5]
- 以3为结尾的最长上升子序列为:[2,3]
- 以7为结尾的最长上升子序列为:[2,3,7]
- 以101为结尾的最长上升子序列为:[2,3,7,101]
- 以18为结尾的最长上升子序列为:[2,3,7,18]
- 由上面的分析可知,以101为结尾的最长上升子序列是我们要求的最终的结果,并且这个结果的状态可以由前面的状态推出,因此我们设立
dp[i]
这个状态变量表示以nums[i]
为结尾的最长上升子序列。
递推公式:
-
我们可以设立两个指针
i,j
来进行操作,i
指针来遍历nums
的每一个元素,j
指针来遍历nums[i]
之前的所有元素,由于我们要找出最大的上升子序列,所以说每个元素我们都要找到nums中在这个元素之前的所有比这个元素要小的元素,这样才能尽可能的构成最大的递增子序列。 -
所以说我们使用i,j指针来遍历字符串。
-
当
nums[i]>nums[j]
时,意味着我们当前元素大于之前的一个元素,这两个元素之间可以构成一个递增子序列,所以说我们可能要进行更新dp[i],为什么是可能呢?因为我们dp[i]
的值可能比dp[j]+1
(dp[j]+1的意思就是前j个元素构成的递增序列,再加上num[i]这个值的长度)这个值更大,所以说我们得取一个最大的值。 -
因此,递推公式为:
vector<int> dp(nums.size(),1);
int ans=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);
}
ans=max(ans,dp[i]);
}
遍历顺序
- 由于dp[i]是要由它之前的元素dp[j]来推导的,因此遍历顺序明显是从前向后遍历
如何初始化?
- 首先,我们将dp[i]中的所有值全都初始化为1,因为每个元素至少都有一个递增子序列(也就是它本身构成的子序列)
- 然后,依据我们的递推公式从前向后进行初始化操作即可。
举例验证dp数组
- nums数组: [10,9,2,5,3,7,101,18]
- 以10结尾的最长上升子序为:[10]
- 以9为结尾的最长上升子序列为:[9]
- 以2为结尾的最长上升子序列为:[2]
- 以5为结尾的最长上升子序列为:[2,5]
- 以3为结尾的最长上升子序列为:[2,3]
- 以7为结尾的最长上升子序列为:[2,3,7]
- 以101为结尾的最长上升子序列为:[2,3,7,101]
- 以18为结尾的最长上升子序列为:[2,3,7,18]
- 这个例子也说明了我们的dp数组是正确的
代码实现
class Solution {
public:
int lengthOfLIS(vector<int>& nums) {
vector<int> dp(nums.size(),1);
//这个初始值为1,因为至少都有长度为1的递增子序列
int ans=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);
}
ans=max(ans,dp[i]);
}
return ans;
}
};