300. 最长递增子序列

https://leetcode-cn.com/problems/longest-increasing-subsequence/

class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        int n = nums.size();
        vector<int> dp(n, 1);
        for (int i = 1; i < nums.size(); i++) {
            int max_length = 1;
            for (int j = 0; j < i; j++) {
                if (nums[j] < nums[i]) {
                    max_length = max(max_length, dp[j]);
                    dp[i] = max(dp[i], max_length+1);
                }
            }
        }
        int res = 1;
        for (int i = 0; i < n; i++) {
            res = max(dp[i], res);
        }
        return res;
    }
};

思路

重启dp训练的第一题，有点绕。

定义dp[i]是最难的，因为这就是子问题啊。这个地方绕的地方在于dp[i]和求解目标不一致，最终目标还需要遍历dp数组max一下；有的dp就不需要max, dp[i]就是答案。这个需要好好体会。

为啥这个dp[i]不定义成最终目标啊，因为以求解目标定义dp[i]你就找不到递推关系，这样的dp[i]就不是子问题，所以找准子问题才是最难的。

既然是子序列，就是不连续的，所以i不一定拼在i-1后，可以拼在[0, i-1]范围的任何谁之后，那肯定挑最长的去拼。你想在『它』后面拼接，所以上一个子问题必须以『它』结尾。
在它前面比它小的元素里，挑最长的在后面拼。（这个过程用题目给的例子，手动求一下dp[i]画一画）

泛化

image.png

这个状态定义方法是很常见的，记住这个套路。至少可以泛化到『最长上升子串』。

image.png