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訓(xùn)練的第一題蛮瞄，有點(diǎn)繞。
定義dp[i]是最難的，因?yàn)檫@就是子問題啊简软。這個(gè)地方繞的地方在于dp[i]和求解目標(biāo)不一致谊惭，最終目標(biāo)還需要遍歷dp數(shù)組max一下逛球；有的dp就不需要max, dp[i]就是答案蕴忆。這個(gè)需要好好體會(huì)仗岖。
為啥這個(gè)dp[i]不定義成最終目標(biāo)啊金麸，因?yàn)橐郧蠼饽繕?biāo)定義dp[i]你就找不到遞推關(guān)系擎析，這樣的dp[i]就不是子問題，所以找準(zhǔn)子問題才是最難的挥下。
既然是子序列揍魂，就是不連續(xù)的，所以i不一定拼在i-1后棚瘟，可以拼在[0, i-1]范圍的任何誰之后现斋，那肯定挑最長的去拼。你想在『它』后面拼接偎蘸，所以上一個(gè)子問題必須以『它』結(jié)尾庄蹋。
在它前面比它小的元素里瞬内，挑最長的在后面拼。（這個(gè)過程用題目給的例子限书，手動(dòng)求一下dp[i]畫一畫）
泛化
image.png
這個(gè)狀態(tài)定義方法是很常見的虫蝶，記住這個(gè)套路。至少可以泛化到『最長上升子串』倦西。
image.png
