【算法】【动规】最长递增子序列

本文主要是介绍【算法】【动规】最长递增子序列，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

跳转汇总链接

👉🔗动态规划算法汇总链接

2.1 最长递增子序列

🔗题目链接

给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。子序列是由数组派生而来的序列，删除（或不删除）数组中的元素而 不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。

状态表示
- 本题依旧以 nums 字符串上 i 位置为结尾作为一个状态；
- dp[i] 表示，以 i 为结尾的所有子序列中，最长的严格递增子序列的长度。
状态转移方程
- 分析 dp 表，分成两种情况，第一种是自身，第二种是之前的最大递增子序列+自身
- 同时要考虑第二种情况下，能否满足成为一个严格递增子序列，这里设自身的上一个位置为 j（0 <= j < i）。
- ```
dp[i] 的两种填写情况，if 长度为1，1if 长度大于1，(在 0 <= j< i 的范围内，nums[j]<nums[i] 的情况下) 取 dp[j]+1 的最大值
```
初始化
- dp 表都初始化为 1。
填表顺序
- 从左往右依次填写。
返回值
- 整张 dp 表的最大值

class Solution {
public:int lengthOfLIS(vector<int>& nums) {int n = nums.size();vector<int> dp(n, 1);int maxRet = 1;for(int i = 1; i < n; i++){for(int j = 0; j < i; j++){if(nums[j] < nums[i]){dp[i] = max(dp[j] + 1, dp[i]);}}       maxRet = max(maxRet, dp[i]);}return maxRet;}
};