摘要

• 如果答案在dp數(shù)組中的位置不是固定的，可以在dp數(shù)組的更新過(guò)程中記錄可能的答案，簡(jiǎn)化代碼，例如今天的三道題，都可以在每次更新dp數(shù)組后來(lái)記錄最大值。

• 通過(guò)dp數(shù)組的定義中的下標(biāo)偏移（+1或-1等等），在dp數(shù)組中添加初始行和初始列，可以簡(jiǎn)化初始化邏輯和下標(biāo)越界判斷。

LeetCode300 最長(zhǎng)遞增子序列

300. 最長(zhǎng)遞增子序列 - 力扣（Leetcode）

• 初見(jiàn)題目的想法：每個(gè)數(shù)字都有可能作為最長(zhǎng)遞增子序列的結(jié)束，且以nums[i]作為結(jié)束的遞增子序列的最小長(zhǎng)度是1，dp[i]是以nums[i]作為結(jié)束的遞增子序列的最長(zhǎng)長(zhǎng)度，假設(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;
    }
};

• 還是按步驟來(lái)思考如何使用動(dòng)態(tài)規(guī)劃來(lái)解決這道題
• dp數(shù)組及下標(biāo)的含義：dp[i]是以nums[i]作為結(jié)束的遞增子序列的最長(zhǎng)長(zhǎng)度。
• 確定遞推公式，假設(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é)尾的序列后，此時(shí)不需要更新dp數(shù)組。
• 確定如何初始化dp數(shù)組，根據(jù)dp數(shù)組的定義，以nums[i]結(jié)尾的遞增序列的長(zhǎng)度至少是1，即序列至少包含nums[i]自身，所以dp數(shù)組所有的值初始化為1。
• 遍歷順序：dp[i]是由j < i的dp[j]推導(dǎo)而來(lái)的，所以應(yīng)該從小到大遍歷i；而對(duì)于選定了i之后，只需要遍歷所有的 ，j從小到大還是從大到小都可以。

題解代碼如下，記錄最大值的操作可以放在dp數(shù)組的更新中，簡(jiǎn)化代碼

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 最長(zhǎng)連續(xù)遞增子序列

674. 最長(zhǎng)連續(xù)遞增序列 - 力扣（Leetcode）

• 初見(jiàn)題目的想法：其實(shí)這就是在上一題的基礎(chǔ)上對(duì)j做了限制，因?yàn)橐ＷC遞增子序列中的元素在原序列中連續(xù)，所以nums[i]只能接在以nums[i - 1]，為結(jié)尾的子序列上，那么根據(jù)dp數(shù)組的定義，對(duì)于j < i，能取的j其實(shí)只有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;
    }
};

其實(shí)max(dp[i], dp[i - 1] + 1)也沒(méi)有必要，因?yàn)?code>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;
    }
};

• 然后還是按動(dòng)規(guī)的步驟來(lái)分析這道題
• dp數(shù)組及數(shù)組下標(biāo)的含義：dp[i]表示的是以nums[i]為結(jié)尾的遞增子序列的最長(zhǎng)長(zhǎng)度。
• 遞推公式：因?yàn)橄拗屏诉B續(xù)，所以dp[i]要么由dp[i-1]推導(dǎo)而來(lái)，要么保持初始值。所以
• 遍歷順序：i從小到大遍歷，因?yàn)?code>dp[i]依賴于dp[i-1]。

LeetCode718 最長(zhǎng)重復(fù)子數(shù)組

718. 最長(zhǎng)重復(fù)子數(shù)組 - 力扣（Leetcode）

• dp數(shù)組及數(shù)組下標(biāo)的含義：dp[i][j]的含義是，以nums1[i - 1]為結(jié)尾的nums1的子數(shù)組和以nums2[j - 1]為結(jié)尾的nums2的子數(shù)組，兩者的最長(zhǎng)重復(fù)部分的長(zhǎng)度為dp[i][j]。這樣定義dp數(shù)組可以為初始化和實(shí)現(xiàn)代碼提供便利。另外，要注意的是，子數(shù)組是連續(xù)的子序列。怎么體現(xiàn)“連續(xù)”呢？
• 確定遞推公式：
  • 如果nums1[i-1] == nums2[j-1]，那么說(shuō)明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)而來(lái)。
  • 如果nums1[i-1]接在nums1[i-2]為結(jié)尾的nums1的子數(shù)組后，nums[j-1]可以接在nums[j-2]為結(jié)尾的子數(shù)組后，且nums1[i-1] == nums[j-1]，那么重復(fù)子序列的長(zhǎng)度就可以+1，即
  • 在同一次比較中，i和j應(yīng)該是同進(jìn)同退的。如果在同一次比較中取比較i和j-1，或者比較i-1和j，就不算是同一次比較了，因?yàn)檫@樣相當(dāng)于考慮另外的子數(shù)組的可能。實(shí)際上i和j不同進(jìn)同退的話也很難寫出邏輯清晰的實(shí)現(xiàn)代碼。這或許體現(xiàn)出了“連續(xù)”子序列，因?yàn)槿绻?code>i和j不同進(jìn)同退，就可能導(dǎo)致某一方的子序列是“斷開(kāi)”的。這樣說(shuō)可能還是太抽象了，畢竟dp數(shù)組的定義完全沒(méi)有提到連續(xù)，只能通過(guò)遞推公式去控制“連續(xù)”。
• 確定dp數(shù)組如何初始化，dp數(shù)組的定義為dp數(shù)組的初始化提供了方便，
  • dp[i][0]和dp[0][j]的含義實(shí)際上沒(méi)有意義，因?yàn)闀?huì)出現(xiàn)-1的下標(biāo)，那應(yīng)該初始化成什么值呢，只有初始化成0是不影響之后的dp數(shù)組的計(jì)算的，因?yàn)橹貜?fù)子序列的長(zhǎng)度肯定是從0開(kāi)始累加的。
  • 實(shí)際上，這相當(dāng)于用額外空間簡(jiǎn)化了初始化過(guò)程，也簡(jiǎn)化了邊界條件的判斷。
• 確定遍歷順序，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ù)組的更新過(guò)程。

• 那么，還是回到?jīng)]解決的問(wèn)題上來(lái)，怎么體現(xiàn)“連續(xù)”？
  • dp[i][j]表示以nums1[i-1]結(jié)尾的nums1的子序列和以nums[j-1]結(jié)尾的nums2的子序列，兩者的最長(zhǎng)重復(fù)部分的長(zhǎng)度為dp[i][j]?；仡?code>dp數(shù)組的定義，這可沒(méi)提到“連續(xù)”。
  • 我目前的理解是，“連續(xù)”體現(xiàn)在遞推公式和dp數(shù)組的更新過(guò)程中，因?yàn)橐陨戏治鰶](méi)有考慮nums1[i-1] != nums2[j-1]的情況，也就是nums1[i-1]和nums2[i-1]接不上的情況，只有能接上的時(shí)候才更新dp數(shù)組，那其實(shí)也就只考慮了連續(xù)的情況，隱式地忽略了那些不連續(xù)的情況。
  • 如果不要求連續(xù)的話，假設(shè)nums1[i-1] != nums2[j-1]，可以更新dp數(shù)組嗎？根據(jù)經(jīng)驗(yàn)，可能會(huì)這樣來(lái)更新：dp[i][j]=dp[i-1][j-1]，根據(jù)dp數(shù)組的定義來(lái)理解就是nums1[i-1]和nums[j-1]接不上了，但是之前的以nums1[i-1-1]為結(jié)尾和nums2[j-1-1]為結(jié)尾的公共子數(shù)組是可以的。但是，這就違反了dp數(shù)組的定義，因?yàn)槲覀兠鞔_要求的是以nums1[i-1]結(jié)尾和以nums2[j-1]結(jié)尾，而不是“嘗試到”nums1[i-1]和nums[j-1]
  • 所以，dp數(shù)組的定義其實(shí)也暗含了"連續(xù)"，因?yàn)?code>dp數(shù)組的定義明確指定了子序列以什么作為結(jié)尾，這一點(diǎn)和第二天要寫的 1143. 最長(zhǎng)公共子序列 - 力扣（Leetcode）是不一樣的！

dp 數(shù)組定義的問(wèn)題

• 如果這樣來(lái)定義dp數(shù)組：dp[i][j]的含義是，以nums1[i]為結(jié)尾的nums1的子數(shù)組和以nums2[j]為結(jié)尾的nums2的子數(shù)組，兩者的最長(zhǎng)重復(fù)部分的長(zhǎng)度為dp[i][j]。會(huì)怎么樣呢？
• 分析的過(guò)程就不贅述了，只是從dp數(shù)組的下標(biāo)到nums1和nums2的數(shù)組下標(biāo)的對(duì)應(yīng)關(guān)系變化了，dp[i][j]對(duì)應(yīng)的不再是nums1[i-1]和nums2[j-1]，而是直接對(duì)應(yīng)nums[i]和nums[j]。
• 初始化也有變化，如果nums1[i] 與nums2[0]相同的話，對(duì)應(yīng)的dp[i][0]就要初始化為1， 因?yàn)榇藭r(shí)最長(zhǎng)重復(fù)子數(shù)組為1。nums2[j]與nums1[0]相同的話，同理。
  • 相當(dāng)于假設(shè)了nums1[i]與nums2[0]相等，nums2[j]與nums1[0]相等，因?yàn)樵?code>dp數(shù)組的更新過(guò)程中，由于下標(biāo)不能出現(xiàn)負(fù)數(shù)，不會(huì)再更新dp[i][0]和dp[0][j]。所以這樣定義dp數(shù)組似乎也不算很直觀。
• 由于下標(biāo)不能出現(xiàn)負(fù)數(shù)，還要添加邊界條件判斷。

使用這樣的定義的dp數(shù)組的實(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));

        // 要對(duì)第一行，第一列進(jìn)行初始化
        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)負(fù)數(shù)
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                }
                res = max(res, dp[i][j]);
            }
        }
        return res;
    }
};

• 可見(jiàn)，通過(guò)dp數(shù)組的定義中的下標(biāo)偏移，在dp數(shù)組中添加初始行和初始列，可以簡(jiǎn)化初始化邏輯和下標(biāo)越界判斷。