300.longest-increasing-subsequence 最长递增子序列

问题描述

300.最长递增子序列

解题思路

关键在于，dp[i]表示什么含义便于解这道题，子序列不一定连续，所以为了便于求解，dp[i]应该表示为以nums[i - 1]结尾的最长严格递增子序列的长度；

递推关系为:

if (nums[i - 1] > nums[j - 1]) // j < i，表示nums[i - 1]前的任意一个元素
    dp[i] = max(dp[j] + 1, dp[i])

代码

class Solution {
  public:
    int lengthOfLIS(vector<int> &nums) {
        vector<int> dp(nums.size() + 1, 1); // dp[0]不考虑，至少有一个元素，所以初始化为1
        // dp[1] = 1;
        // int index = 0;
        int m = 0;
        for (int i = 1; i <= nums.size(); i++) {
            for (int j = 1; j < i; j++) {
                if (nums[i - 1] > nums[j - 1])
                    dp[i] = max(dp[j] + 1, dp[i]);
            }
            if (dp[i] > m)
                m = dp[i];
        }
        return m;
    }
};