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

2023-12-16 22:11:59

跳转汇总链接

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


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;
    }
};

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


文章来源:https://blog.csdn.net/m0_67470729/article/details/135035440
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。