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
