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

跳转汇总链接

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

2.1 最长递增子序列

🔗题目链接

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

1. 状态表示
   • 本题依旧以 nums 字符串上 i 位置为结尾作为一个状态；
   • dp[i] 表示，以 i 为结尾的所有子序列中，最长的严格递增子序列的长度。
2. 状态转移方程
   • 分析 dp 表，分成两种情况，第一种是自身，第二种是之前的最大递增子序列+自身
   • 同时要考虑第二种情况下，能否满足成为一个严格递增子序列，这里设自身的上一个位置为 j（0 <= j < i）。

   • dp[i] 的两种填写情况，
     	if 长度为1，1
     	if 长度大于1，(在 0 <= j< i 的范围内，nums[j]<nums[i] 的情况下) 取 dp[j]+1 的最大值
     

3. 初始化
   • dp 表都初始化为 1。
4. 填表顺序
   • 从左往右依次填写。
5. 返回值
   • 整张 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;
    }
};

🥰如果本文对你有些帮助，欢迎👉 点赞 收藏 关注，你的支持是对作者大大莫大的鼓励！！(????) 若有差错恳请留言指正~~