摘要
如果答案在
dp數(shù)組中的位置不是固定的苹熏，可以在dp數(shù)組的更新過程中記錄可能的答案，簡化代碼币喧，例如今天的三道題轨域，都可以在每次更新dp數(shù)組后來記錄最大值。通過
dp數(shù)組的定義中的下標偏移（+1或-1等等）杀餐，在dp數(shù)組中添加初始行和初始列干发，可以簡化初始化邏輯和下標越界判斷。
LeetCode300 最長遞增子序列
- 初見題目的想法：每個數(shù)字都有可能作為最長遞增子序列的結(jié)束史翘，且以
nums[i]作為結(jié)束的遞增子序列的最小長度是1枉长，dp[i]是以nums[i]作為結(jié)束的遞增子序列的最長長度冀续，假設(shè)j < i，根據(jù)dp數(shù)組的定義必峰，如果num[j] < nums[i]洪唐，nums[i]可以接在以nums[j]為結(jié)尾的序列上，則dp[i] = dp[j] + 1吼蚁；如果nums[j] >= nums[i]桐罕，則nums[i]不能接在以nums[j]結(jié)尾的序列上。由此得到遞推公式：
題解代碼如下
class Solution {
public:
int lengthOfLIS(vector<int>& nums) {
vector<int> dp(nums.size(), 1);
for (int i = 0; i < nums.size(); i++) {
for (int j = 0; j < i; j++) {
if (nums[j] < nums[i]) dp[i] = max(dp[i], dp[j] + 1);
}
}
int res = INT_MIN;
for (int i = 0; i < nums.size(); i++)
res = max(res, dp[i]);
return res;
}
};
- 還是按步驟來思考如何使用動態(tài)規(guī)劃來解決這道題
-
dp數(shù)組及下標的含義：dp[i]是以nums[i]作為結(jié)束的遞增子序列的最長長度桂敛。 - 確定遞推公式，假設(shè)
j < i溅潜，根據(jù)dp數(shù)組的定義- 如果
nums[j] < nums[i]术唬，則nums[i]能接在以nums[j]為結(jié)尾的序列后，假設(shè)dp[j]是已知的滚澜，那么粗仓。
- 如果
nums[j] >= nums[i]，則nums[i]不能接在以nums[j]為結(jié)尾的序列后设捐，此時不需要更新dp數(shù)組借浊。
- 如果
- 確定如何初始化
dp數(shù)組，根據(jù)dp數(shù)組的定義萝招，以nums[i]結(jié)尾的遞增序列的長度至少是1蚂斤，即序列至少包含nums[i]自身，所以dp數(shù)組所有的值初始化為1槐沼。 - 遍歷順序：
dp[i]是由j < i的dp[j]推導(dǎo)而來的曙蒸，所以應(yīng)該從小到大遍歷i；而對于選定了i之后岗钩，只需要遍歷所有的纽窟，
j從小到大還是從大到小都可以。
題解代碼如下兼吓，記錄最大值的操作可以放在dp數(shù)組的更新中臂港，簡化代碼
class Solution {
public:
int lengthOfLIS(vector<int>& nums) {
vector<int> dp(nums.size(), 1);
int res = INT_MIN;
for (int i = 0; i < nums.size(); i++) {
for (int j = 0; j < i; j++) {
if (nums[j] < nums[i]) dp[i] = max(dp[i], dp[j] + 1);
}
res = max(res, dp[i]);
}
return res;
}
};
LeetCode674 最長連續(xù)遞增子序列
- 初見題目的想法：其實這就是在上一題的基礎(chǔ)上對
j做了限制，因為要保證遞增子序列中的元素在原序列中連續(xù)视搏，所以nums[i]只能接在以nums[i - 1]审孽，為結(jié)尾的子序列上，那么根據(jù)dp數(shù)組的定義浑娜，對于j < i瓷胧，能取的j其實只有i - 1了。
題解代碼如下
class Solution {
public:
int findLengthOfLCIS(vector<int>& nums) {
vector<int> dp(nums.size(), 1);
int res = 1;
for (int i = 1; i < nums.size(); i++) {
if (nums[i - 1] < nums[i]) dp[i] = max(dp[i], dp[i - 1] + 1);
res = max(res, dp[i]);
}
return res;
}
};
其實max(dp[i], dp[i - 1] + 1)也沒有必要棚愤，因為dp[i]只可能被更新一次搓萧，如果dp[i]被更新杂数，那肯定比初始的值要大。
class Solution {
public:
int findLengthOfLCIS(vector<int>& nums) {
vector<int> dp(nums.size(), 1);
int res = 1;
for (int i = 1; i < nums.size(); i++) {
if (nums[i - 1] < nums[i]) dp[i] = dp[i - 1] + 1;
res = max(res, dp[i]);
}
return res;
}
};
- 然后還是按動規(guī)的步驟來分析這道題
-
dp數(shù)組及數(shù)組下標的含義：dp[i]表示的是以nums[i]為結(jié)尾的遞增子序列的最長長度瘸洛。 - 遞推公式：因為限制了連續(xù)揍移，所以
dp[i]要么由dp[i-1]推導(dǎo)而來，要么保持初始值反肋。所以 - 遍歷順序：
i從小到大遍歷那伐，因為dp[i]依賴于dp[i-1]。
LeetCode718 最長重復(fù)子數(shù)組
-
dp數(shù)組及數(shù)組下標的含義：dp[i][j]的含義是石蔗，以nums1[i - 1]為結(jié)尾的nums1的子數(shù)組和以nums2[j - 1]為結(jié)尾的nums2的子數(shù)組罕邀，兩者的最長重復(fù)部分的長度為dp[i][j]。這樣定義dp數(shù)組可以為初始化和實現(xiàn)代碼提供便利养距。另外诉探，要注意的是，子數(shù)組是連續(xù)的子序列棍厌。怎么體現(xiàn)“連續(xù)”呢肾胯？ - 確定遞推公式：
- 如果
nums1[i-1] == nums2[j-1]，那么說明nums1[i-1]可以接在nums1[i-2]為結(jié)尾的nums1的子數(shù)組后耘纱，nums[j-1]可以接在nums[j-2]為結(jié)尾的子數(shù)組后敬肚，所以dp[i][j]應(yīng)該由dp[i-1][j-1]推導(dǎo)而來。 - 如果
nums1[i-1]接在nums1[i-2]為結(jié)尾的nums1的子數(shù)組后束析，nums[j-1]可以接在nums[j-2]為結(jié)尾的子數(shù)組后艳馒，且nums1[i-1] == nums[j-1]，那么重復(fù)子序列的長度就可以+1员寇，即 - 在同一次比較中鹰溜，
i和j應(yīng)該是同進同退的。如果在同一次比較中取比較i和j-1丁恭，或者比較i-1和j曹动，就不算是同一次比較了，因為這樣相當(dāng)于考慮另外的子數(shù)組的可能牲览。實際上i和j不同進同退的話也很難寫出邏輯清晰的實現(xiàn)代碼墓陈。這或許體現(xiàn)出了“連續(xù)”子序列，因為如果i和j不同進同退第献，就可能導(dǎo)致某一方的子序列是“斷開”的贡必。這樣說可能還是太抽象了，畢竟dp數(shù)組的定義完全沒有提到連續(xù)庸毫，只能通過遞推公式去控制“連續(xù)”仔拟。
- 如果
- 確定
dp數(shù)組如何初始化，dp數(shù)組的定義為dp數(shù)組的初始化提供了方便飒赃，-
dp[i][0]和dp[0][j]的含義實際上沒有意義利花，因為會出現(xiàn)-1的下標科侈，那應(yīng)該初始化成什么值呢，只有初始化成0是不影響之后的dp數(shù)組的計算的炒事，因為重復(fù)子序列的長度肯定是從0開始累加的臀栈。 - 實際上，這相當(dāng)于用額外空間簡化了初始化過程挠乳，也簡化了邊界條件的判斷权薯。
-
- 確定遍歷順序，
dp[i][j]依賴于dp[i-1][j-1]睡扬，所以i和j都應(yīng)該從小到大遍歷盟蚣。
題解代碼如下
class Solution {
public:
int findLength(vector<int>& nums1, vector<int>& nums2) {
vector<vector<int>> dp(nums1.size() + 1, vector<int>(nums2.size() + 1, 0));
int res = 0;
for (int i = 1; i <= nums1.size(); i++) {
for (int j = 1; j <= nums2.size(); j++) {
if (nums1[i - 1] == nums2[j - 1]) {
dp[i][j] = dp[i - 1][j - 1] + 1;
}
res = max(res, dp[i][j]);
}
}
return res;
}
};
以nums1 = [1,2,3,2,1]; nums2 = [3,2,1,4,7]為例，模擬dp數(shù)組的更新過程卖怜。
- 那么屎开，還是回到?jīng)]解決的問題上來，怎么體現(xiàn)“連續(xù)”韧涨？
-
dp[i][j]表示以nums1[i-1]結(jié)尾的nums1的子序列和以nums[j-1]結(jié)尾的nums2的子序列，兩者的最長重復(fù)部分的長度為dp[i][j]侮繁÷侵啵回顧dp數(shù)組的定義，這可沒提到“連續(xù)”宪哩。 - 我目前的理解是娩贷，“連續(xù)”體現(xiàn)在遞推公式和
dp數(shù)組的更新過程中，因為以上分析沒有考慮nums1[i-1] != nums2[j-1]的情況锁孟，也就是nums1[i-1]和nums2[i-1]接不上的情況彬祖，只有能接上的時候才更新dp數(shù)組，那其實也就只考慮了連續(xù)的情況品抽，隱式地忽略了那些不連續(xù)的情況储笑。 - 如果不要求連續(xù)的話，假設(shè)
nums1[i-1] != nums2[j-1]圆恤，可以更新dp數(shù)組嗎突倍？根據(jù)經(jīng)驗，可能會這樣來更新：dp[i][j]=dp[i-1][j-1]盆昙，根據(jù)dp數(shù)組的定義來理解就是nums1[i-1]和nums[j-1]接不上了羽历，但是之前的以nums1[i-1-1]為結(jié)尾和nums2[j-1-1]為結(jié)尾的公共子數(shù)組是可以的。但是淡喜，這就違反了dp數(shù)組的定義秕磷，因為我們明確要求的是以nums1[i-1]結(jié)尾和以nums2[j-1]結(jié)尾，而不是“嘗試到”nums1[i-1]和nums[j-1] - 所以炼团，
dp數(shù)組的定義其實也暗含了"連續(xù)"澎嚣，因為dp數(shù)組的定義明確指定了子序列以什么作為結(jié)尾疏尿，這一點和第二天要寫的 1143. 最長公共子序列 - 力扣（Leetcode）是不一樣的！
-
dp 數(shù)組定義的問題
- 如果這樣來定義
dp數(shù)組：dp[i][j]的含義是币叹，以nums1[i]為結(jié)尾的nums1的子數(shù)組和以nums2[j]為結(jié)尾的nums2的子數(shù)組润歉，兩者的最長重復(fù)部分的長度為dp[i][j]。會怎么樣呢颈抚？ - 分析的過程就不贅述了踩衩，只是從
dp數(shù)組的下標到nums1和nums2的數(shù)組下標的對應(yīng)關(guān)系變化了，dp[i][j]對應(yīng)的不再是nums1[i-1]和nums2[j-1]贩汉，而是直接對應(yīng)nums[i]和nums[j]驱富。 - 初始化也有變化，如果
nums1[i]與nums2[0]相同的話匹舞，對應(yīng)的dp[i][0]就要初始化為1褐鸥， 因為此時最長重復(fù)子數(shù)組為1。nums2[j]與nums1[0]相同的話赐稽，同理叫榕。- 相當(dāng)于假設(shè)了
nums1[i]與nums2[0]相等，nums2[j]與nums1[0]相等姊舵，因為在dp數(shù)組的更新過程中晰绎，由于下標不能出現(xiàn)負數(shù)，不會再更新dp[i][0]和dp[0][j]括丁。所以這樣定義dp數(shù)組似乎也不算很直觀荞下。
- 相當(dāng)于假設(shè)了
- 由于下標不能出現(xiàn)負數(shù)，還要添加邊界條件判斷史飞。
使用這樣的定義的dp數(shù)組的實現(xiàn)代碼如下
class Solution {
public:
int findLength(vector<int>& nums1, vector<int>& nums2) {
vector<vector<int>> dp (nums1.size() + 1, vector<int>(nums2.size() + 1, 0));
// 要對第一行尖昏，第一列進行初始化
for (int i = 0; i < nums1.size(); i++) if (nums1[i] == nums2[0]) dp[i][0] = 1;
for (int j = 0; j < nums2.size(); j++) if (nums1[0] == nums2[j]) dp[0][j] = 1;
int res = 0;
for (int i = 0; i < nums1.size(); i++) {
for (int j = 0; j < nums2.size(); j++) {
if (nums1[i] == nums2[j] && i && j) { // 防止 i-1,j-1 出現(xiàn)負數(shù)
dp[i][j] = dp[i - 1][j - 1] + 1;
}
res = max(res, dp[i][j]);
}
}
return res;
}
};
- 可見，通過
dp數(shù)組的定義中的下標偏移构资，在dp數(shù)組中添加初始行和初始列抽诉，可以簡化初始化邏輯和下標越界判斷。
