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

一.题目解析:子序列不一定是连续的,但是是严格递增的算法讲解:1.状态表示:dp[i]表示以i位置为结尾,子序列的长度最长2.状态转移方程3.初始化我们单独一个就可以看作是形成一个子序列,所以我们将dp表初始化为14.填表顺序从左向右5.返回值返回dp表的最大值二.代码实现class Solution { public: int lengthOfLIS(vectorint nums) { int nnums.size(); vectorintdp(n,1);//初始化为1,我们单独就可以形成一个子序列 int ret1; for(int i1;in;i) { for(int j0;ji;j) { if(nums[j]nums[i]) dp[i]max(dp[i],dp[j]1); retmax(dp[i],ret); } } return ret; } };