动态规划_最长递增子序列_C++

一.题目解析:

子序列不一定是连续的,但是是严格递增的

算法讲解:

1.状态表示:

dp[i]表示以i位置为结尾,子序列的长度最长

2.状态转移方程

3.初始化

我们单独一个就可以看作是形成一个子序列,所以我们将dp表初始化为1

4.填表顺序

从左向右

5.返回值

返回dp表的最大值

二.代码实现

class Solution { public: int lengthOfLIS(vector<int>& nums) { int n=nums.size(); vector<int>dp(n,1);//初始化为1,我们单独就可以形成一个子序列 int ret=1; for(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); ret=max(dp[i],ret); } } return ret; } };