leetcode

300.最长递增子序列

力扣链接

动规五部曲

1. 确定用作状态转移的dp数组的下标及含义 dp[i] 以nums[i]结尾的最长递增子序列的长度
2. 动规核心 状态转移方程/递推公式 dp[j] = max(dp[i]+1, dp[j])
3. dp数组如何初始化 dp[0]=1 不能为空，至少要包含一个数nums[i]
4. 确定遍历顺序 i从左向右遍历 j正序或反序遍历都行
5. 打印dp数组用于排错

class Solution {
public:
    int lengthOfLIS(std::vector<int>& nums) {
        // nums[j]结尾的数组的最长严格递增子序列的长度为dp[j]
        // 每一个i，对应的dp[i]（即最长递增子序列）起始大小至少是1
        std::vector<int> dp(nums.size(), 1);
        // 此处的res包括上一行全部初始化成1 因为最长严格递增子序列的长度至少为1
        int res=1; 
        for (int j=1;j<nums.size();j++){
            for(int i=0;i<j;i++)
                if (nums[j]>nums[i])
                    dp[j] = std::max(dp[i]+1, dp[j]);
            res = std::max(res, dp[j]);// res 可写到内层for循环里
        }
        return res;
    }
};

This site is open source. Improve this page.