LeetCode300.最长递增子序列

LeetCode300.最长递增子序列

力扣题目链接(opens new window)

给你一个整数数组 nums ,找到其中最长严格递增子序列的长度。

子序列是由数组派生而来的序列,删除(或不删除)数组中的元素而不改变其余元素的顺序。例如,[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。

示例 1:

  • 输入:nums = [10,9,2,5,3,7,101,18]
  • 输出:4
  • 解释:最长递增子序列是 [2,3,7,101],因此长度为 4 。

示例 2:

  • 输入:nums = [0,1,0,3,2,3]
  • 输出:4

示例 3:

  • 输入:nums = [7,7,7,7,7,7,7]
  • 输出:1

提示:

  • 1 <= nums.length <= 2500
  • -104 <= nums[i] <= 104

动态规划思路讲解

状态变量以及其含义

  • 我们设置状态变量dp[i],表示以nums[i]为结尾的最长上升子序列的长度
  • 我们举个例子,以示例1为例,我们来推导一下为什么可以用dp[i]来表示以nums[i]为结尾的最长上升子序列
  • nums数组: [10,9,2,5,3,7,101,18]
  1. 以10结尾的最长上升子序为:[10]
  2. 以9为结尾的最长上升子序列为:[9]
  3. 以2为结尾的最长上升子序列为:[2]
  4. 以5为结尾的最长上升子序列为:[2,5]
  5. 以3为结尾的最长上升子序列为:[2,3]
  6. 以7为结尾的最长上升子序列为:[2,3,7]
  7. 以101为结尾的最长上升子序列为:[2,3,7,101]
  8. 以18为结尾的最长上升子序列为:[2,3,7,18]
  • 由上面的分析可知,以101为结尾的最长上升子序列是我们要求的最终的结果,并且这个结果的状态可以由前面的状态推出,因此我们设立dp[i]这个状态变量表示以nums[i]为结尾的最长上升子序列。

递推公式:

  • 我们可以设立两个指针i,j来进行操作,i指针来遍历nums的每一个元素,j指针来遍历nums[i]之前的所有元素,由于我们要找出最大的上升子序列,所以说每个元素我们都要找到nums中在这个元素之前的所有比这个元素要小的元素,这样才能尽可能的构成最大的递增子序列。

  • 所以说我们使用i,j指针来遍历字符串。

  • nums[i]>nums[j]时,意味着我们当前元素大于之前的一个元素,这两个元素之间可以构成一个递增子序列,所以说我们可能要进行更新dp[i],为什么是可能呢?因为我们dp[i]的值可能比dp[j]+1(dp[j]+1的意思就是前j个元素构成的递增序列,再加上num[i]这个值的长度)这个值更大,所以说我们得取一个最大的值。

  • 因此,递推公式为:

        vector<int> dp(nums.size(),1);
        int ans=1;
        for(int i=1;i<nums.size();i++){
            for(int j=0;j<i;j++){
                if(nums[i]>nums[j]) dp[i]=max(dp[i],dp[j]+1);
            }
            ans=max(ans,dp[i]);
        }

遍历顺序

  • 由于dp[i]是要由它之前的元素dp[j]来推导的,因此遍历顺序明显是从前向后遍历

如何初始化?

  • 首先,我们将dp[i]中的所有值全都初始化为1,因为每个元素至少都有一个递增子序列(也就是它本身构成的子序列)
  • 然后,依据我们的递推公式从前向后进行初始化操作即可。

举例验证dp数组

  • nums数组: [10,9,2,5,3,7,101,18]
  1. 以10结尾的最长上升子序为:[10]
  2. 以9为结尾的最长上升子序列为:[9]
  3. 以2为结尾的最长上升子序列为:[2]
  4. 以5为结尾的最长上升子序列为:[2,5]
  5. 以3为结尾的最长上升子序列为:[2,3]
  6. 以7为结尾的最长上升子序列为:[2,3,7]
  7. 以101为结尾的最长上升子序列为:[2,3,7,101]
  8. 以18为结尾的最长上升子序列为:[2,3,7,18]
  • 这个例子也说明了我们的dp数组是正确的

代码实现

class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        vector<int> dp(nums.size(),1);
        //这个初始值为1,因为至少都有长度为1的递增子序列
        int ans=1;
        for(int i=1;i<nums.size();i++){
            for(int j=0;j<i;j++){
                if(nums[i]>nums[j]) dp[i]=max(dp[i],dp[j]+1);
            }
            ans=max(ans,dp[i]);
        }
        return ans;
    }
};