?問題匯總：

1.如何選擇使用遞歸法解題還是迭代法解題

（我猜是做的多了背的題多了就自然懂了）

2.迭代法有沒有可以去重的空間和套路

迭代法一般沒有通用去重方式,因?yàn)橐呀?jīng)相當(dāng)于遞歸去重后了

這兩個(gè)問題其實(shí)是一個(gè)問題,一般直接寫出的沒有去重的遞歸法,復(fù)雜度很高,此時(shí)需要使用備忘錄去重,而備忘錄去重時(shí)間復(fù)雜度和使用dp數(shù)組進(jìn)行迭代求解時(shí)間復(fù)雜度相同,但是由于遞歸需要反復(fù)調(diào)用函數(shù),實(shí)際開銷更加多

綜上,一般使用dp數(shù)組法最優(yōu)

一、動(dòng)態(tài)規(guī)劃基本框架

1.1 動(dòng)態(tài)規(guī)劃用于解決的問題？（如何判斷能否使用dp）

動(dòng)態(tài)規(guī)劃 = 最優(yōu)子結(jié)構(gòu) + 重疊子問題 + 轉(zhuǎn)移方程

最優(yōu)子結(jié)構(gòu)保證能從局部解推出全局解，也就是保證能夠?qū)懗鲛D(zhuǎn)移方程

重疊子問題說明暴力解法太耗時(shí)，我們可以使用動(dòng)態(tài)規(guī)劃進(jìn)行優(yōu)化

（期待后期的更改，相信未來的我的智慧?。?/p>

「最優(yōu)子結(jié)構(gòu)」是某些問題的一種特定性質(zhì)，并不是動(dòng)態(tài)規(guī)劃問題專有的。也就是說，很多問題其實(shí)都具有最優(yōu)子結(jié)構(gòu)，只是其中大部分不具有重疊子問題，所以我們不把它們歸為動(dòng)態(tài)規(guī)劃系列問題而已。

我先舉個(gè)很容易理解的例子：假設(shè)你們學(xué)校有 10 個(gè)班，你已經(jīng)計(jì)算出了每個(gè)班的最高考試成績(jī)。那么現(xiàn)在我要求你計(jì)算全校最高的成績(jī)，你會(huì)不會(huì)算？當(dāng)然會(huì)，而且你不用重新遍歷全校學(xué)生的分?jǐn)?shù)進(jìn)行比較，而是只要在這 10 個(gè)最高成績(jī)中取最大的就是全校的最高成績(jī)。

我給你提出的這個(gè)問題就符合最優(yōu)子結(jié)構(gòu)：可以從子問題的最優(yōu)結(jié)果推出更大規(guī)模問題的最優(yōu)結(jié)果。讓你算每個(gè)班的最優(yōu)成績(jī)就是子問題，你知道所有子問題的答案后，就可以借此推出全校學(xué)生的最優(yōu)成績(jī)這個(gè)規(guī)模更大的問題的答案。

你看，這么簡(jiǎn)單的問題都有最優(yōu)子結(jié)構(gòu)性質(zhì)，只是因?yàn)轱@然沒有重疊子問題，所以我們簡(jiǎn)單地求最值肯定用不出動(dòng)態(tài)規(guī)劃。

再舉個(gè)例子：假設(shè)你們學(xué)校有 10 個(gè)班，你已知每個(gè)班的最大分?jǐn)?shù)差（最高分和最低分的差值）。那么現(xiàn)在我讓你計(jì)算全校學(xué)生中的最大分?jǐn)?shù)差，你會(huì)不會(huì)算？可以想辦法算，但是肯定不能通過已知的這 10 個(gè)班的最大分?jǐn)?shù)差推到出來。因?yàn)檫@ 10 個(gè)班的最大分?jǐn)?shù)差不一定就包含全校學(xué)生的最大分?jǐn)?shù)差，比如全校的最大分?jǐn)?shù)差可能是 3 班的最高分和 6 班的最低分之差。

這次我給你提出的問題就不符合最優(yōu)子結(jié)構(gòu)，因?yàn)槟銢]辦通過每個(gè)班的最優(yōu)值推出全校的最優(yōu)值，沒辦法通過子問題的最優(yōu)值推出規(guī)模更大的問題的最優(yōu)值。前文?動(dòng)態(tài)規(guī)劃詳解?說過，想滿足最優(yōu)子結(jié)，子問題之間必須互相獨(dú)立。全校的最大分?jǐn)?shù)差可能出現(xiàn)在兩個(gè)班之間，顯然子問題不獨(dú)立，所以這個(gè)問題本身不符合最優(yōu)子結(jié)構(gòu)。

那么遇到這種最優(yōu)子結(jié)構(gòu)失效情況，怎么辦？策略是：改造問題。對(duì)于最大分?jǐn)?shù)差這個(gè)問題，我們不是沒辦法利用已知的每個(gè)班的分?jǐn)?shù)差嗎，那我只能這樣寫一段暴力代碼：

int result = 0;
for (Student a : school) {
    for (Student b : school) {
        if (a is b) continue;
        result = max(result, |a.score - b.score|);
    }
}
return result;

改造問題，也就是把問題等價(jià)轉(zhuǎn)化：最大分?jǐn)?shù)差，不就等價(jià)于最高分?jǐn)?shù)和最低分?jǐn)?shù)的差么，那不就是要求最高和最低分?jǐn)?shù)么，不就是我們討論的第一個(gè)問題么，不就具有最優(yōu)子結(jié)構(gòu)了么？那現(xiàn)在改變思路，借助最優(yōu)子結(jié)構(gòu)解決最值問題，再回過頭解決最大分?jǐn)?shù)差問題，是不是就高效多了？

1.2 迭代（自底向上）-五部曲（自底向上的迭代求解）

1.2.1 明確dp數(shù)組下標(biāo)和下標(biāo)對(duì)應(yīng)的值的含義

這一步其實(shí)是要和轉(zhuǎn)移方程結(jié)合理解的，很多時(shí)候我們是為了能夠?qū)懗鲛D(zhuǎn)移方程，才進(jìn)行某種dp數(shù)組的定義

所以這一步非常重要，我們需要知道問題中有哪些狀態(tài)才能為dp數(shù)組合理分配這些狀態(tài)

所謂狀態(tài)，也就是原問題和子問題中會(huì)變化的變量。我們要將這些變化的量分配給dp數(shù)組的下標(biāo)和值

注意：比較難的題，狀態(tài)不能一眼看出來，需要我們自己進(jìn)行構(gòu)造，這樣的題只有靠積累

簡(jiǎn)單例子

1：斐波那契的dp[]定義：i 表示n = i，dp[i]表示n = i對(duì)應(yīng)的結(jié)果是什么，這樣的邏輯非常清晰

?

2：湊零錢：（注意雖然硬幣個(gè)數(shù)不會(huì)變化，因?yàn)橛矌艛?shù)量無限，所以有兩個(gè)變化量，湊零錢的硬幣數(shù)和目標(biāo)金額），所以我們定義i為目標(biāo)金額，dp[i]值為零錢個(gè)數(shù)（一般都會(huì)吧dp[i]當(dāng)作輸出結(jié)果）

這里會(huì)有一點(diǎn)歧義 ，我們要知道我們最后要得到的是什么，應(yīng)該是amount對(duì)應(yīng)的最小數(shù)量，那么dp[i]應(yīng)該設(shè)置為金額i對(duì)應(yīng)的最小數(shù)量，不要思考成我們將dp[i]定義為i對(duì)應(yīng)的所有數(shù)量，然后通過比較所有dp[i]來求得最小值，這樣似乎更容易理解，但是卻不實(shí)際，那樣dp[i]會(huì)被定義為二維數(shù)組，復(fù)雜度也上升了

我們應(yīng)該知道，最小這個(gè)限制，是在轉(zhuǎn)移方程里面實(shí)現(xiàn)的，所以我們默認(rèn)得到的dp[i]就是最小值！

困難例子

最長(zhǎng)遞增子序列：我們發(fā)現(xiàn)問題中貌似沒有直接給出變化的狀態(tài)，從而無從下手

這是子序列問題中的一類問題，處理方法有相對(duì)固定幾類，我們這里就直接套用經(jīng)典定義

dp[i]?表示以?nums[i]?這個(gè)數(shù)結(jié)尾的最長(zhǎng)遞增子序列的長(zhǎng)度。

對(duì)于其他不明確狀態(tài)的問題如何定義，這個(gè)也要靠積累，需要我們多做題才知道

1.2.2 確定遞推公式（轉(zhuǎn)移方程）

動(dòng)態(tài)規(guī)劃的核心設(shè)計(jì)思想是數(shù)學(xué)歸納法。

相信大家對(duì)數(shù)學(xué)歸納法都不陌生，高中就學(xué)過，而且思路很簡(jiǎn)單。比如我們想證明一個(gè)數(shù)學(xué)結(jié)論，那么我們先假設(shè)這個(gè)結(jié)論在?k < n?時(shí)成立，然后根據(jù)這個(gè)假設(shè)，想辦法推導(dǎo)證明出?k = n?的時(shí)候此結(jié)論也成立。如果能夠證明出來，那么就說明這個(gè)結(jié)論對(duì)于?k?等于任何數(shù)都成立。

類似的，我們?cè)O(shè)計(jì)動(dòng)態(tài)規(guī)劃算法，不是需要一個(gè) dp 數(shù)組嗎？我們可以假設(shè)?dp[0...i-1]?都已經(jīng)被算出來了，然后問自己：怎么通過這些結(jié)果算出?dp[i]？

直接拿最長(zhǎng)遞增子序列這個(gè)問題舉例你就明白了。不過，首先要定義清楚 dp 數(shù)組的含義，即?dp[i]?的值到底代表著什么？

我們的定義是這樣的：dp[i]?表示以?nums[i]?這個(gè)數(shù)結(jié)尾的最長(zhǎng)遞增子序列的長(zhǎng)度（子序列中要包含nums[i],可能我們會(huì)想這樣不能找到實(shí)際的最大子序列，但是其實(shí)我們遍歷了所有nums[i]，并不會(huì)漏掉）。

假設(shè)我們已經(jīng)知道了?dp[0..4]?的所有結(jié)果，我們?nèi)绾瓮ㄟ^這些已知結(jié)果推出?dp[5]?

這就是求解轉(zhuǎn)移方程的重點(diǎn)一步，此處

根據(jù)剛才我們對(duì)?dp?數(shù)組的定義，現(xiàn)在想求?dp[5]?的值，也就是想求以?nums[5]?為結(jié)尾的最長(zhǎng)遞增子序列。

其實(shí)就是自己總結(jié)規(guī)律，然后使用數(shù)學(xué)歸納法驗(yàn)證

光靠腦袋想dp的遞推公式確實(shí)很困難 我的做法是畫一個(gè)dp數(shù)組出來 找一個(gè)例子填進(jìn)去,然后通過觀察找出規(guī)律倒推遞推公式(僅供參考,有待驗(yàn)證)

當(dāng)我們發(fā)現(xiàn)遞推公式不好找時(shí),需要思考是否改變dp定義

nums[5] = 3，既然是遞增子序列，我們只要找到前面那些結(jié)尾比 3 小的子序列，然后把 3 接到這些子序列末尾，就可以形成一個(gè)新的遞增子序列，而且這個(gè)新的子序列長(zhǎng)度加一。

同時(shí)我們是在找最長(zhǎng)的子序列，所以我們需要找出前面序列中的最長(zhǎng)序列接上去

我們的轉(zhuǎn)移方程為：

dp[i] = dp[j] + 1;//j是比i小的數(shù)

?接下來就是要將取最大值還有求比i小的j結(jié)合起來

代碼如下：

    for(int j = 0;j < i;j++){        
        if (nums[i] > nums[j]) {
            // 把 nums[i] 接在后面，即可形成長(zhǎng)度為 dp[j] + 1，
            // 且以 nums[i] 為結(jié)尾的遞增子序列
            dp[i] = Math.max(dp[i], dp[j] + 1);
        }
    }

這整個(gè)代碼才是完整的轉(zhuǎn)移方程?

一個(gè)重點(diǎn)：

我們一定要假設(shè)已經(jīng)知道了dp[i-1]，并且我們?cè)O(shè)置的dp數(shù)組可以存放的值就是我們希望的值

1.2.3 dp數(shù)組初始化和base case

初始化要結(jié)合我們對(duì)dp數(shù)組的定義進(jìn)行設(shè)置，并且結(jié)合保證在執(zhí)行max和min操作時(shí)不會(huì)影響更新值，對(duì)dp數(shù)組的定義不同的話，初始化也會(huì)有差別

（有其他理解后面補(bǔ)充）

base case 就是遞歸中的最底層，是所有子問題中的最基礎(chǔ)的問題，靠這個(gè)問題推出其他所有解

初始化非常重要，它和轉(zhuǎn)移方程共同決定了我們定義的dp[i]里面的值是否正確,一般是確定了dp定義和轉(zhuǎn)移方程,再開始初始化

1.2.4 確定遍歷順序

現(xiàn)在接觸到的都是順序進(jìn)行遍歷的，并沒有在遍歷時(shí)挖坑，但是后面有從前往后，從后往前還有斜著遍歷

這些情況的分析等到做到具體的題目再來補(bǔ)充

將轉(zhuǎn)移方程放入遍歷中：

        for(int i = 0;i < nums.size();i++)
            for(int j = 0;j < i;j++){
                if(nums[i] > nums[j]){
                    dp[i] = max(dp[i],dp[j]+1);
                }
            }

1.2.5 dp數(shù)組打印

通過遞推公式手寫出dp數(shù)組，用于檢測(cè)dp哪里寫錯(cuò)了

1.3 遞歸（自頂向上）

1.3.1 暴力解法

按道理來說，應(yīng)該是先寫出遞歸法，然后通過備忘錄進(jìn)行優(yōu)化，再然后使用dp數(shù)組的解法來解答，這里由于dp數(shù)組法有一套成熟的流程，我這里想寫遞歸法時(shí)，會(huì)將迭代法先寫出來，然后使用套用到遞歸中。

1.3.2 備忘錄去重

明確了問題，其實(shí)就已經(jīng)把問題解決了一半。即然耗時(shí)的原因是重復(fù)計(jì)算，那么我們可以造一個(gè)「?jìng)渫洝?，每次算出某個(gè)子問題的答案后別急著返回，先記到「?jìng)渫洝估镌俜祷?；每次遇到一個(gè)子問題先去「?jìng)渫洝估锊橐徊?，如果發(fā)現(xiàn)之前已經(jīng)解決過這個(gè)問題了，直接把答案拿出來用，不要再耗時(shí)去計(jì)算了。

注意：遞歸法使用備忘錄去重后，盡管時(shí)間復(fù)雜度和迭代相同，但是，我們遞歸會(huì)不斷的在棧上調(diào)用函數(shù)，造成大量的內(nèi)存和時(shí)間消耗，這會(huì)導(dǎo)致實(shí)際運(yùn)行時(shí)，遞歸法的時(shí)間空間消耗大于迭代法

詳情參考：

第七章 C語(yǔ)言函數(shù)_遞歸函數(shù)的致命缺陷：巨大的時(shí)間開銷和內(nèi)存開銷(附帶優(yōu)化方案)_c++ 遞歸資源消耗-CSDN博客

1.3.3 dp table去重

就是迭代法，這樣的做法時(shí)間復(fù)雜度和備忘錄去重一致

二、經(jīng)典dp問題-用于理解dp的做法和細(xì)節(jié)

2.1 零錢兌換

題目鏈接：322. 零錢兌換 - 力扣（LeetCode）

?

(1)dp定義:

首先確定狀態(tài)，問題中改變的狀態(tài)只有總金額和使用的硬幣個(gè)數(shù)（硬幣總數(shù)無限，所以剩下的硬幣數(shù)量不變化）

我們將dp[i]和i與變化量進(jìn)行匹配，從而有如下設(shè)置：

i為總金額。dp[i]為達(dá)到總金額i需要的硬幣數(shù)量

(2)轉(zhuǎn)移方程

我們這樣想，肯定是要建立dp[i]和dp[j]的聯(lián)系，但實(shí)際這個(gè)i j應(yīng)該如何取，也就是總金額如何變化更合理，所以自然想到了，每次對(duì)總金額 i 減少一個(gè)硬幣的值，來求得 j ，那么關(guān)系如何建立呢

這就要用到上面的數(shù)學(xué)歸納法了，假設(shè)我們已經(jīng)知道減少一個(gè)硬幣后的dp[i - coin]的值，那么dp[i]的最小值就是dp[i - coin]+1

(3)初始化

由于我們的i要索引到amount，索引dp的size要為amount+1，同時(shí)對(duì)于dp[i]來說，最差的情況即使由i個(gè)一元硬幣組成，那么最大個(gè)數(shù)為i，為了使得初始狀態(tài)不影響結(jié)果，需要將dp[i] 賦值 i+1，為了省事直接賦值最大的amount+1，代碼如下：

vector<int> dp(amount+1,amount+1);

對(duì)于base case，我們知道dp[0] = 0，但是注意dp[1] != 1,因?yàn)橛幸粋€(gè)硬幣但不一定是一個(gè)一元的硬幣，所有可能dp[1] = -1,因此不能將dp[1]放入base case中，代碼如下：

        dp[0] = 0;
        // dp[1] = 1;

(4)確定遍歷方向:

此題為順序遍歷，但是也要仔細(xì)理解一下

非常類似bfs的理解過程，我們先對(duì)dp[i]中所有金額從0-amount進(jìn)行遍歷，保證能夠處理到所有的i（類似于走通每一層），然后對(duì)于每一個(gè)i我們都將所有的coin去除一次（所有的選擇都選一次），選出最小的情況然后賦值給dp[i]

代碼如下：

        for(int i = 0;i < amount+1;i++)
            for(int coin : coins){
                if(i - coin < 0)continue;
                dp[i] = min(dp[i],dp[i - coin] + 1);
            }

5 ：打印dp數(shù)組進(jìn)行debug，此題過程比較簡(jiǎn)單就不演示了

完整代碼如下：

class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        vector<int> dp(amount+1,amount+1);
        if(amount == 0)return 0;
        dp[0] = 0;
        // dp[1] = 1;
        for(int i = 0;i < amount+1;i++)
            for(int coin : coins){
                if(i - coin < 0)continue;
                dp[i] = min(dp[i],dp[i - coin] + 1);
            }
        return dp[amount] == amount+1 ? -1 : dp[amount];
    }
};

2.2 斐波那契數(shù)列

題目鏈接：509. 斐波那契數(shù) - 力扣（LeetCode）

此題已經(jīng)給出轉(zhuǎn)移方程，并且dp數(shù)組的定義也較為清楚，base case給出，初始化時(shí)沒有特殊要求，我們直接初始化為0就行了，并且也是順序遍歷，所有很容易寫出如下代碼：

class Solution {
public:
    int fib(int n) {
        if(n==0) return 0;
        vector<int> dp(n+1,0);
        dp[0] = 0;
        dp[1] = 1;
        for(int i = 2;i <= n;i++)
            dp[i] = dp[i-1] +dp[i-2];
        return dp[n];
    }
};

由于只涉及到兩個(gè)數(shù)的處理，所以我們可以只保留這兩個(gè)數(shù)，有如下優(yōu)化代碼：

class Solution {
public:
    int fib(int n) {
        if(n==0)return 0;
        if(n==1)return 1;
        int p=0,q=1,res=0;
        for(int i = 2;i <= n;i++){
            res = p + q;
            p = q;
            q = res;
        }
        return res;
    }
};

?三、子序列問題

子序列子串問題總結(jié):

1.dp定義

一般有兩種dp定義

1)dp[i]表示以nums[i]結(jié)尾(包含i)的結(jié)果

2)dp[i]表示以[0,i]的子串(不要求包含i)的結(jié)果

單序列問題,一般使用(1),因?yàn)橹挥幸粭l單序列,(1)更容易將前后關(guān)系鏈接起來

雙序列問題:
一般要求連續(xù)(子串,子數(shù)組)就使用(1),不連續(xù)(子序列)就使用(2)

(注意:為例初始化方便,一般的dp[i][j]對(duì)應(yīng)nums[i-1]和nums2[j-1])

2.轉(zhuǎn)移方程

轉(zhuǎn)移方程的確立本質(zhì)上就是分情況討論

對(duì)于單序列,我們一般會(huì)判斷nums[i]和nums[i-1]的關(guān)系,或者判斷dp[i-1]等等,分情況討論如何從dp[i-1]轉(zhuǎn)移到dp[i]

(單序列的判斷更加靈活)

對(duì)于雙序列問題,一般會(huì)對(duì)比nums1[i]和nums2[j],通常相同時(shí),我們考慮dp[i-1][j-1]轉(zhuǎn)移到dp[i][j],而不同時(shí)考慮dp[i-1][j-1],dp[i][j-1],dp[i-1][j]如何轉(zhuǎn)移到dp[i][j],例如下圖:

如何轉(zhuǎn)移?
一般都是通過+的形式進(jìn)行轉(zhuǎn)移

3.初始化

這一步需要在轉(zhuǎn)移方程之后寫,因?yàn)槲覀円_定轉(zhuǎn)移方程可行,才能開始初始化,首先我們要畫出如下的dp數(shù)組(此處針對(duì)雙序列,單序列一般只初始化dp[0])

?根據(jù)dp數(shù)組定義在橙色位置填上初始值,然后可以使用轉(zhuǎn)移方程檢查一下合理

圖中紅字很重要

4.遍歷順序

從初始化開始往后遍歷即可,類似下圖:

5.檢查dp數(shù)組

覺得有問題,就把dp數(shù)組打印出來,?看和畫的一樣不

3.1單序列問題

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

題目鏈接：300. 最長(zhǎng)遞增子序列 - 力扣（LeetCode）

1：首先確定如何定義dp數(shù)組

我們使用子序列一般定義方式，定義dp[i]為以nums[i]結(jié)尾的子序列的解（也即是這一部分的嚴(yán)格遞增子序列最大長(zhǎng)度）?,注意：這里特別還有一點(diǎn)，求得的最大子序列必須包含nums[i]，為了和之后的轉(zhuǎn)移方程進(jìn)行匹配

2：確定轉(zhuǎn)移方程

轉(zhuǎn)移方程的確定一定要根據(jù)數(shù)學(xué)歸納法來求解，因?yàn)槲覀円骴p[nums.size()],所以我們假設(shè)知道dp[0,.....,nums.size()-1]，直接理解不是很清晰，作圖如下：

為了推導(dǎo)到更一般的情況，我們假設(shè)前面已知的為dp[i]，當(dāng)前需要求得的時(shí)dp[j]，因?yàn)槊恳粋€(gè)子序列的解必須包含nums[i]，所以如果當(dāng)前的nums[j]比前面某一個(gè)nums[i]大的話，就可以直接接在后面，那么dp[j]的解至少也是dp[i]+1。

最后想要求得dp[j]實(shí)際上比dp[i]大多少，我們只需要比較所有比nums[j]小的nums[i]，選取最大的dp[i]進(jìn)行+1即可

因此轉(zhuǎn)移方程為：

for(int i = 0;i < j; i++)
    if(nums[j] > nums[i])
        dp[j] = max(dp[j],dp[i]+1)

3:確定初始狀態(tài)

由于dp[i]表示nums[i]結(jié)尾且包含nums[i]的解，所有解的長(zhǎng)度至少為1，也就是nums[i]本身，因此我們需要對(duì)dp[i]初始化為1；

4：遍歷順序

由于我們求解dp[j]時(shí)會(huì)用到dp[0,..,j-1]所有我們順序遍歷即可

5：打印dp

完整代碼如下：

dp數(shù)組法

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

時(shí)間復(fù)雜度O(n^2)

此題有一種更加巧妙的解法,可以進(jìn)一步降低時(shí)間復(fù)雜度:

二分法:

    int lengthOfLIS(vector<int>& nums) {
        int piles = 0;    // 牌堆數(shù)初始化為 0
        vector<int> top(nums.size());   // 牌堆數(shù)組 top
        
        for (int i = 0; i < nums.size(); i++) {
            int poker = nums[i];    // 要處理的撲克牌

            /***** 搜索左側(cè)邊界的二分查找 *****/
            int left = 0, right = piles;    // 搜索區(qū)間為 [left, right)
            while (left < right) {
                int mid = (left + right) / 2;    // 防溢出
                if (top[mid] > poker) {
                    right = mid;
                } else if (top[mid] < poker) {
                    left = mid + 1;
                } else {
                    right = mid;
                }
            }
            /*********************************/

            // 沒找到合適的牌堆，新建一堆
            if (left == piles) piles++;
            // 把這張牌放到牌堆頂
            top[left] = poker;
        }
        // 牌堆數(shù)就是 LIS 長(zhǎng)度
        return piles;
    }

時(shí)間復(fù)雜度O(n*log2n)?

?3.1.2? 俄羅斯套娃信封

?此題為最長(zhǎng)遞增遞增子序列的二維形式,本質(zhì)還是找形狀遞增的最長(zhǎng)子信封,主要問題在于,我們?nèi)绾螌⑿螤钜脒M(jìn)行比較

此處處理十分的巧妙:

先對(duì)寬度?w?進(jìn)行升序排序，如果遇到?w?相同的情況，則按照高度?h?降序排序；之后把所有的?h?作為一個(gè)數(shù)組，在這個(gè)數(shù)組上計(jì)算 LIS 的長(zhǎng)度就是答案。

為什么是這樣呢,因?yàn)槲覀兿仁沟脤挾扰藕眯?然后對(duì)高度求最長(zhǎng)遞增子序列,就能得到遞增的信封,但是考慮到相同寬度不能相互裝,也即是同一寬度我們只能使用一個(gè)信封,所以我們選擇將同一寬度下的高度進(jìn)行降序,這樣在降序中,只有可能取其中之一(因?yàn)槲覀冋业氖巧蚺帕??

?lambda

這里引入lambda表達(dá)式進(jìn)行排序:

c++ lambda 看這篇就夠了?。ㄓ悬c(diǎn)詳細(xì)）_c++ 運(yùn)行時(shí) 構(gòu)建 lamda-CSDN博客

        sort(envelopes.begin(), envelopes.end(), 
            [](const vector<int> a, const vector<int>& b) {
                // return a[0] == b[0] ? b[1] - a[1] : a[0] - b[0];
                if (a[0] != b[0]) {
                    return a[0] < b[0]; // 按寬度升序排序
                } else {
                    return a[1] > b[1]; // 如果寬度相同，按高度升序排序
                }
                });

然后我們對(duì)排好序的信封的高進(jìn)行最長(zhǎng)遞增子序列求解,直接調(diào)用函數(shù)即可

dp數(shù)組法:

    int maxseq(vector<int>& seq) {
        int size = seq.size(),res= 0;
        vector<int> dp(size,1);
        dp[0] = 1;
        for(int i = 0;i< size;i++){
            for(int j = 0;j< i;j++){
                if(seq[i] > seq[j]){
                    dp[i] = max(dp[i],dp[j]+1);
                }
            }
            res = max(dp[i],res);   
        }
        return res;
    }

二分法:

    int lengthOfLIS(vector<int>& nums) {
        int piles = 0;    // 牌堆數(shù)初始化為 0
        vector<int> top(nums.size());   // 牌堆數(shù)組 top
        
        for (int i = 0; i < nums.size(); i++) {
            int poker = nums[i];    // 要處理的撲克牌

            /***** 搜索左側(cè)邊界的二分查找 *****/
            int left = 0, right = piles;    // 搜索區(qū)間為 [left, right)
            while (left < right) {
                int mid = (left + right) / 2;    // 防溢出
                if (top[mid] > poker) {
                    right = mid;
                } else if (top[mid] < poker) {
                    left = mid + 1;
                } else {
                    right = mid;
                }
            }
            /*********************************/

            // 沒找到合適的牌堆，新建一堆
            if (left == piles) piles++;
            // 把這張牌放到牌堆頂
            top[left] = poker;
        }
        // 牌堆數(shù)就是 LIS 長(zhǎng)度
        return piles;
    }

值得一提的是,本題由于一些惡心的例子,只有使用二分法求解遞增子序列才不會(huì)超時(shí)

完整代碼如下:

class Solution {
public:
//超時(shí)
    int maxseq(vector<int>& seq) {
        int size = seq.size(),res= 0;
        vector<int> dp(size,1);
        dp[0] = 1;
        for(int i = 0;i< size;i++){
            for(int j = 0;j< i;j++){
                if(seq[i] > seq[j]){
                    dp[i] = max(dp[i],dp[j]+1);
                }
            }
            res = max(dp[i],res);   
        }
        return res;
    }
//不超時(shí)
    int lengthOfLIS(vector<int>& nums) {
        int piles = 0;    // 牌堆數(shù)初始化為 0
        vector<int> top(nums.size());   // 牌堆數(shù)組 top
        
        for (int i = 0; i < nums.size(); i++) {
            int poker = nums[i];    // 要處理的撲克牌

            /***** 搜索左側(cè)邊界的二分查找 *****/
            int left = 0, right = piles;    // 搜索區(qū)間為 [left, right)
            while (left < right) {
                int mid = (left + right) / 2;    // 防溢出
                if (top[mid] > poker) {
                    right = mid;
                } else if (top[mid] < poker) {
                    left = mid + 1;
                } else {
                    right = mid;
                }
            }
            /*********************************/

            // 沒找到合適的牌堆，新建一堆
            if (left == piles) piles++;
            // 把這張牌放到牌堆頂
            top[left] = poker;
        }
        // 牌堆數(shù)就是 LIS 長(zhǎng)度
        return piles;
    }

    int maxEnvelopes(vector<vector<int>>& envelopes) {
        int n = envelopes.size();
        // 按寬度升序排列，如果寬度一樣，則按高度降序排列
        sort(envelopes.begin(), envelopes.end(), 
            [](const vector<int> a, const vector<int>& b) {
                // return a[0] == b[0] ? b[1] - a[1] : a[0] - b[0];
                if (a[0] != b[0]) {
                    return a[0] < b[0]; // 按寬度升序排序
                } else {
                    return a[1] > b[1]; // 如果寬度相同，按高度升序排序
                }
                });

        // 對(duì)高度數(shù)組尋找 LIS
        vector<int> height(n);
        for (int i = 0; i < n; i++){
            height[i] = envelopes[i][1];
            // cout<<envelopes[i][0]<<envelopes[i][1]<<endl;
        }
        return lengthOfLIS(height);
    }
};

3.1.3?最長(zhǎng)連續(xù)遞增子序列?

題目鏈接:674. 最長(zhǎng)連續(xù)遞增序列 - 力扣（LeetCode）

因?yàn)橐筮B續(xù)，所以我們對(duì)在上一題基礎(chǔ)上，只對(duì)相鄰兩個(gè)值進(jìn)行判斷，?轉(zhuǎn)移方程如下：

            if(nums[i] > nums[i-1])
                dp[i] = dp[i-1]+1;
            res = max(res,dp[i]);

完整代碼如下:

class Solution {
public:
    int findLengthOfLCIS(vector<int>& nums) {
        if(nums.size()==0)return 0;
        int res =1;
        vector<int> dp(nums.size(),1);
        for(int i = 1;i < nums.size() ;i++){
            if(nums[i] > nums[i-1])
                dp[i] = dp[i-1]+1;
            res = max(res,dp[i]);//上一題的優(yōu)化部分，邊求解邊求最大值，省時(shí)間
        }
        
        return res;
    }
};

3.1.4?最大子序列和--轉(zhuǎn)移方程涉及對(duì)以nums[i]結(jié)尾的理解

?dp定義:

dp[i]：包括下標(biāo)i（以nums[i]為結(jié)尾）的最大連續(xù)子序列和為dp[i]。

?轉(zhuǎn)移方程:

依據(jù)題意,我們會(huì)很自然的想到,要通過nums[i]是否讓子序列繼續(xù)保持增長(zhǎng)來作為判斷條件,但事實(shí)上這樣無法判斷,因?yàn)楫?dāng)nums[i]+dp[i-1] < dp[i-1]時(shí),也可能保留原序列繼續(xù)擴(kuò)展,如圖:

因此我們重新思考判斷條件,首先我們要明確,得到的子序列要以nums[i]結(jié)尾,所以必須以nums[i]為基準(zhǔn)進(jìn)行參考,也就是先思考一定要留下nums[i],再思考是否留下前面的子序列,應(yīng)該是考慮dp[i-1]是否大于0,dp[i-1]大于0的話,nums[i]為結(jié)尾的子序列可以增加,那么可以將nums[i]接到前面子序列的后面,如果dp[i-1]小于0,那么?ums[i]為結(jié)尾的子序列加上dp[i-1]就會(huì)減少,所以我們直接保留nums[i]即可,因此代碼如下圖:

            if(dp[i-1] < 0)
            dp[i] = nums[i];
            else
            dp[i] = dp[i-1] + nums[i];

簡(jiǎn)化一下:

            dp[i] = max(dp[i-1]+nums[i],nums[i]);

初始化

因?yàn)閐p[i]由dp[i-1]決定,那么dp[0]就是最開始的初始狀態(tài).
?根據(jù)dp[i]的定義，很明顯dp[0]應(yīng)為nums[0]即dp[0] = nums[0]

確定遍歷順序

遞推公式中dp[i]依賴于dp[i - 1]的狀態(tài)，需要從前向后遍歷。

完整代碼如下:

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int n = nums.size(),res = INT_MIN;
        vector<int> dp(nums);
        res = dp[0];// 因?yàn)檠h(huán)是從1開始，遍歷不到0，所以此處直接將nums【0】賦給res，模擬一個(gè)第一輪
        for(int i = 1;i < n;i++){
            // if(dp[i-1] < 0)
            // dp[i] = nums[i];
            // else
            // dp[i] = dp[i-1] + nums[i];
            dp[i] = max(dp[i-1]+nums[i],nums[i]);
            res= max(dp[i],res);
        }
        return res;
    }   
};

注意此處,res不是從0開始進(jìn)行遍歷的,那么會(huì)漏掉對(duì)dp[0]的比較,所以我們需要將dp[0]初始化為res的初值(為了不再后面再進(jìn)行一層循環(huán)來求解res的最大值)

由于這里dp[i]只和dp[i-1]有關(guān),所以我們可以使用狀態(tài)壓縮,使用兩個(gè)變量保持dp[i]和dp[i-1]而不使用dp數(shù)組,這樣空間復(fù)雜度會(huì)進(jìn)一步降低

//狀態(tài)壓縮
class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int n = nums.size(),res = INT_MIN;
        int dp_0=nums[0],dp_1;
        res = nums[0];
        for(int i = 1;i < n;i++){
            dp_1 = max(dp_0+nums[i],nums[i]);
            dp_0 = dp_1;
            res= max(dp_1,res);
        }
        return res;
    }   
};

此題還可以使用雙指針進(jìn)行解答,代碼如下,具體解釋減數(shù)組雙指針一節(jié):

// 雙指針法
class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        // if(nums.size()==1)return nums[0];
        int l=0,r=0;
        int sum=0,maxsum=INT_MIN;
        cout<<maxsum;
        while(r<nums.size()){
            sum+=nums[r];
            maxsum = max(maxsum,sum);
            while(sum<0){
                sum-=nums[l];
                // maxsum = max(maxsum,sum);
                l++;
            }
            r++;
        }
        
        return maxsum;
    }
};

3.2?雙序列問題

3.2.1 編輯距離--很重要的母體

?

?迭代法：

?定義：

和一般的子序列問題一樣，我們對(duì)dp數(shù)組的定義為：

dp[i][j]? 為以word1[i-1]和word2[j-1]結(jié)尾的兩個(gè)字符串的編輯距離?

為了方便初始化,后面會(huì)細(xì)說?

?轉(zhuǎn)移方程：
這里的轉(zhuǎn)移方程是最復(fù)雜的，我們要分別求解不同操作對(duì)dp[i][j]的影響。

注意：我們要從后往前操作，因?yàn)樵谇懊娌迦霑?huì)導(dǎo)致前面字符的索引更改?。?！

比較word1[i]和word2[j]?

插入和刪除：

dp[i][j] = dp[i-1][j]+1//在word1進(jìn)行插入或者刪除

dp[i][j] = dp[i][j-1]+1//在word2進(jìn)行插入或者刪除

替換：

dp[i][j] = dp[i-1][j-1]+1//在word1或者word2進(jìn)行替換

相等：

dp[i][j] = dp[i-1][j-1];

因此，轉(zhuǎn)移方程為：

           if(s1[i-1] == s2[j-1])dp[i][j] = dp[i-1][j-1];
           else{
                dp[i][j] = min(
                        dp[i][j-1]+1,
                        dp[i-1][j]+1,
                        dp[i-1][j-1]+1
                );
           }

初始化 ：
我們要知道，什么時(shí)候能一眼看出答案——當(dāng)其中一個(gè)字符串為空時(shí)，這里就涉及到dp數(shù)組的定義了，因?yàn)槿绻鹍p[i][j]為word1[i]和word2[j]結(jié)尾的子串的編輯距離，那么對(duì)于長(zhǎng)度為0的字符串（空串）就無法定義，因此，我們?cè)O(shè)置dp[i][j] 為word1[i-1]和word2[j-1]結(jié)尾的子串的編輯距離

同時(shí)，注意dp 數(shù)組的每個(gè)維度比相應(yīng)的字符串長(zhǎng)度多一個(gè)單位，以便包含空字符串的情況。這就是為什么數(shù)組大小是 m+1 x n+1。因此初始化如下：

        vector<vector<int>> dp(m+1,vector<int>(n+1,0));
        // for(int i = 0;i < m;i++)
        //     dp[i][0] = i;
        // for(int j = 0;j < n;j++)
        //     dp[0][j] = j;
        for(int i = 0;i < m+1;i++)
            dp[i][0] = i;
        for(int j = 0;j < n+1;j++)
            dp[0][j] = j;

?遍歷順序：

注意，這里我們雖然是從后往前處理，也就是說我們要先知道前面的才能處理后面的，因此遍歷的時(shí)候需要從前往后遍歷

另一方面可以這樣思考：

如圖

可以看出dp[i][j]是依賴左方，上方和左上方元素的，所以在dp矩陣中一定是從左到右從上到下去遍歷。?

將轉(zhuǎn)移方程放入遍歷中：

        for(int i = 1;i <=m ;i++)
            for(int j = 1; j <= n;j++) 
            {
                if(s1[i-1] == s2[j-1])dp[i][j] = dp[i-1][j-1];
                else{
                    dp[i][j] = min(
                        dp[i][j-1]+1,
                        dp[i-1][j]+1,
                        dp[i-1][j-1]+1
                    );
                }
            }

最后，添加特殊處理的部分，代碼如下：

class Solution {
public:
    int min(int a, int b, int c) {
        return std::min(std::min(a, b), c);
    }
    int minDistance(string s1, string s2) {
        int m = s1.size(),n = s2.size();
        if(m==0)return n;
        if(n==0)return m;
        //int* dp = new int[m][n];二維數(shù)組不好使用new的方式進(jìn)行實(shí)現(xiàn)

        //int[][] dp = new int[m + 1][n + 1];這樣是對(duì)的
        vector<vector<int>> dp(m+1,vector<int>(n+1,0));
        for(int i = 0;i < m;i++)
            dp[i][0] = i;
        for(int j = 0;j < n;j++)
            dp[0][j] = j;
        for(int i = 1;i <=m ;i++)
            for(int j = 1; j <= n;j++) 
            {
                if(s1[i-1] == s2[j-1])dp[i][j] = dp[i-1][j-1];
                else{
                    dp[i][j] = min(
                        dp[i][j-1]+1,
                        dp[i-1][j]+1,
                        dp[i-1][j-1]+1
                    );
                }
            }
        return dp[m][n];
    }

};

遞歸法：

先明確遞歸的思路:
我們?nèi)绾螐牡D(zhuǎn)換到遞歸

首先,狀態(tài)轉(zhuǎn)移,初始化和dp的定義是不變的,那么我們首先思考如何將dp[i][j]中的i,j體現(xiàn)在dp遞歸函數(shù)中,顯而易見,答案是,傳入兩個(gè)參數(shù),i,j;

    int dp(string s1,int i,string s2, int j)

接著是初始化，這里本來可以設(shè)置?dp[i][j]? 為以word1[i]和word2[j]結(jié)尾的兩個(gè)字符串的編輯距離，但為了和迭代法統(tǒng)一，就延續(xù)上述設(shè)置

        if(i==0)return j;
        if(j==0)return i;

轉(zhuǎn)移方程，與迭代法十分類似：

        if(s1[i-1] == s2[j-1])return dp(s1,i-1,s2,j-1);
        else return min(
            dp(s1,i-1,s2,j)+1,
            dp(s1,i,s2,j-1)+1,
            dp(s1,i-1,s2,j-1)+1
        );

注意 ，遞歸法有遍歷順序，但是是自動(dòng)執(zhí)行的，遞歸中會(huì)自動(dòng)執(zhí)行，所以迭代法中的for循環(huán)部分可以省去：
完整代碼如下：

class Solution {
public:

    int minDistance(string s1, string s2) {
        int m = s1.length(), n = s2.length();
        return dp(s1, m, s2, n);
    }

    int dp(string s1,int i,string s2, int j){
        if(i==0)return j;
        if(j==0)return i;
        if(s1[i-1] == s2[j-1])return dp(s1,i-1,s2,j-1);
        else return min(
            dp(s1,i-1,s2,j)+1,
            dp(s1,i,s2,j-1)+1,
            dp(s1,i-1,s2,j-1)+1
        );
    }

    int min(int a, int b, int c) {
        return std::min(std::min(a, b), c);
    }
};

遞歸去重：

備忘錄：

我們?cè)黾右粋€(gè)備忘錄，將結(jié)果保存到備忘錄的對(duì)應(yīng)位置

memo = vector<vector<int>>(m+1, vector<int>(n+1, -1));

檢測(cè)這個(gè)位置是否已經(jīng)有值，有的話就不用再算了

        // 查備忘錄，避免重疊子問題
        if (memo[i][j] != -1) {
            return memo[i][j];
        }
        // 狀態(tài)轉(zhuǎn)移，結(jié)果存入備忘錄
        if (s1[i-1] == s2[j-1]) {
            memo[i][j] = dp(s1, i - 1, s2, j - 1);
        } else {
            memo[i][j] = min(
                dp(s1, i, s2, j - 1) + 1,
                dp(s1, i - 1, s2, j) + 1,
                dp(s1, i - 1, s2, j - 1) + 1
            );
        }
        return memo[i][j];

可能會(huì)疑惑，為什么能保證出現(xiàn)過一次的memo[i][j]就一定是最優(yōu)解，后面不會(huì)更新比這個(gè)值更好的解嗎？

我們可以看到，每次求解dp[i][j],都是使用三種狀態(tài)，那么第二次對(duì)dp[i][j]進(jìn)行處理的話，也會(huì)進(jìn)行同樣的處理，結(jié)果是沒變的

因此，完整代碼如下：

class Solution {
public:
    vector<vector<int>> memo;
    int minDistance(string s1, string s2) {
        int m = s1.length(), n = s2.length();
        memo = vector<vector<int>>(m+1,vector<int>(n+1,-1));
        return dp(s1, m, s2, n);
    }


    int dp(string s1,int i,string s2, int j){
        if(i==0)return j;
        if(j==0)return i;
        if(memo[i][j] != -1) return memo[i][j];
        if(s1[i-1] == s2[j-1])memo[i][j] =  dp(s1,i-1,s2,j-1);
        else memo[i][j] = min(
            dp(s1,i-1,s2,j)+1,
            dp(s1,i,s2,j-1)+1,
            dp(s1,i-1,s2,j-1)+1
        );

        return memo[i][j];
    }

    int min(int a, int b, int c) {
        return std::min(std::min(a, b), c);
    }
};

迭代法：

遞歸+備忘錄：

可以看出，迭代法遞歸法復(fù)雜度相同時(shí)，由于遞歸不斷調(diào)用函數(shù)產(chǎn)生資源消耗，其運(yùn)行效率遠(yuǎn)不如迭代法

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

dp數(shù)組（dp table）以及下標(biāo)的含義

?dp[i][j] ：以下標(biāo)i - 1為結(jié)尾的A，和以下標(biāo)j - 1為結(jié)尾的B，最長(zhǎng)重復(fù)子數(shù)組長(zhǎng)度為dp[i][j]。 （特別注意： “以下標(biāo)i - 1為結(jié)尾的A” 標(biāo)明一定是 以A[i-1]為結(jié)尾的字符串 ）

(此處定義同編輯距離,為了初始化方便)

轉(zhuǎn)移方程:

做過編輯距離后發(fā)現(xiàn),此題比較簡(jiǎn)單,因?yàn)槲覀僤p[i][j]必須包含nums1[i-1]和nums2[j-1],所以只需要比較nums1[i-1]和nums[j-1]即可,當(dāng)他們不等時(shí),dp[i][j]=0

因此,轉(zhuǎn)移方程如下:

                if(nums1[i-1] == nums2[j-1]){
                    dp[i][j] = dp[i-1][j-1] + 1;
                    res = max(res,dp[i][j]);
                }

?dp數(shù)組初始化

DP數(shù)組如下,我們發(fā)現(xiàn)我們需要對(duì)第一排和第一列進(jìn)行初始化,才能順利推導(dǎo)到后面的值

根據(jù)dp數(shù)組的意義,我們將其初始化為0即可

同時(shí),由于某些dp值,我們會(huì)賦值為0,所以我們直接將所以初值都設(shè)置為0,當(dāng)遇到應(yīng)該為0的dp值,我們不更新即可,代碼如下:

        vector<vector<int>> dp(nums1.size()+1,vector<int>(nums2.size()+1,0));

遍歷順序:
外層for循環(huán)遍歷A，內(nèi)層for循環(huán)遍歷B。

外層for循環(huán)遍歷B，內(nèi)層for循環(huán)遍歷A。都行

完整代碼如下:

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;
    }
};

3.2.3? 最長(zhǎng)重復(fù)子序列

?本題和最長(zhǎng)重復(fù)子數(shù)組區(qū)別在于這里不要求是連續(xù)的了,所以dp數(shù)組的定義不用必須以nums[i]結(jié)尾了

確定dp數(shù)組（dp table）以及下標(biāo)的含義:

dp[i][j]：長(zhǎng)度為[0, i - 1]的字符串text1與長(zhǎng)度為[0, j - 1]的字符串text2的最長(zhǎng)公共子序列為dp[i][j]

轉(zhuǎn)移方程 :

主要就是兩大情況： text1[i - 1] 與 text2[j - 1]相同，text1[i - 1] 與 text2[j - 1]不相同?

如果text1[i - 1] 與 text2[j - 1]相同，那么找到了一個(gè)公共元素，所以dp[i][j] = dp[i - 1][j - 1] + 1;

如果text1[i - 1] 與 text2[j - 1]不相同，雖然不能直接遞增一位,但是兩邊字符串都增加了一位,這帶來了新的可能性,我們不能從 text1[0,i - 2] 與 text2[0,j - 2]得到結(jié)果,,那就看看text1[0, i - 2]與text2[0, j - 1]的最長(zhǎng)公共子序列 和 text1[0, i - 1]與text2[0, j - 2]的最長(zhǎng)公共子序列，取最大的。

?其實(shí)也就相當(dāng)于,如果我們不能從dp[i-][j-1]推出dp[i][j],那就從dp[i-1][j]和dp[j-1][i]中想辦法,因?yàn)閐p[i-1][j]和dp[j-1][i]時(shí)對(duì)稱的,我們就選擇其中的更大值,如下圖:

代碼如下:

                if(text1[i-1] == text2[j-1]){
                    dp[i][j] = max(dp[i][j],dp[i-1][j-1]+1);
                }
                else{
                    dp[i][j] = max(dp[i-1][j],dp[i][j-1]);
                }

初始化:
?同樣需要第一排和第一列的初值,且初始化都為0

?確定遍歷順序:
從前向后，從上到下,進(jìn)行兩層循環(huán)

?完整代碼:

class Solution {
public:
    int longestCommonSubsequence(string text1, string text2) {
        if(text1.size() == 0 || text2.size() ==0)return 0;
        vector<vector<int>> dp(text1.size()+1,vector<int>(text2.size()+1,0));
    
        for(int i=1;i<=text1.size();i++)
            for(int j =1;j<=text2.size();j++){
                if(text1[i-1] == text2[j-1]){
                    dp[i][j] = max(dp[i][j],dp[i-1][j-1]+1);
                }
                else{
                    dp[i][j] = max(dp[i-1][j],dp[i][j-1]);
                }
            }
        return dp[text1.size()][text2.size()];     
    }

};

這樣的dp定義方式有一個(gè)優(yōu)勢(shì),結(jié)果不用遍歷dp數(shù)組

3.2.4?不相交的線?

本題就是尋找最長(zhǎng)的公共子序列

代碼如下:

class Solution {
public:
    int maxUncrossedLines(vector<int>& nums1, vector<int>& nums2) {
        vector<vector<int>> dp(nums1.size()+1,vector<int>(nums2.size()+1,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] = max(dp[i-1][j-1]+1,dp[i][j]);
                }else{
                    dp[i][j] = max(dp[i][j-1],dp[i-1][j]);
                }
            }
        return dp[nums1.size()][nums2.size()];
    }
};

?3.2.5?判斷子序列

?此題和其他題的區(qū)別在于,返回值位bool,因此會(huì)很容易將dp數(shù)組的值定義為bool型,但這樣初始化很復(fù)雜,時(shí)間復(fù)雜度有點(diǎn)高,初始化如下:

class Solution {
public:
    bool isSubsequence(string s, string t) {
        int n = s.size(),m = t.size();
        vector<vector<bool>> dp(n+1,vector<bool>(m+1));
        for(int i = 0;i <= n;i++){
            dp[i][0] = false;
        }
        for(int j = 0;j <= m;j++){
            dp[0][j] = true;
        }
        for(int i = 1;i <= n;i++){
            for(int j = 1;j <= m;j++){
                if(s[i-1] == t[j-1])
                    dp[i][j] = dp[i-1][j-1];
                else{
                    dp[i][j] = dp[i][j-1];
                }
            }
        }
        return dp[n][m];
    }
};

因此我們選擇dp[i][j]的含義為,有多少個(gè)匹配的字符,當(dāng)匹配字符==s.size()時(shí),就是true?

完整代碼如下:

class Solution {
public:
    bool isSubsequence(string s, string t) {
        int n = s.size(),m = t.size();
        vector<vector<int>> dp(n+1,vector<int>(m+1,0));
        for(int i = 1;i <= n;i++){
            for(int j = 1;j <= m;j++){
                if(s[i-1] == t[j-1])
                    dp[i][j] = dp[i-1][j-1]+1;
                else{
                    dp[i][j] = dp[i][j-1];
                }
            }
        }
        return dp[n][m] == s.size() ? true : false;
    }
};

3.2.6 不同的子序列-雙序列中只改變單序列的典例

(1)dp定義:
?dp[i][j]：以i-1為結(jié)尾的s子序列中出現(xiàn)以j-1為結(jié)尾的t的個(gè)數(shù)為dp[i][j]。

(2)轉(zhuǎn)移方程:
此題與其他題不一樣,因?yàn)槭乔笥卸嗌俜N刪除方法,所以dp數(shù)組的更新不能是簡(jiǎn)單的+1

這里是求總的方法數(shù),那當(dāng) s[i-1]==t[j-1]時(shí):

我們不能只考慮將 s[i-1] 和 t[j-1] 同時(shí)留下,也即是dp[i][j] =dp[i-1][j-1] (最后一位相互抵消了)

還要考慮,如果前面也有一位 s[k] == s[i-1] (且相對(duì)位置滿足t的要求),那么我們可以同時(shí)留下 s[k] 和 t[j-1] ,將 s[i-1] 刪掉,因此dp[i][j] = dp[i-1][j](如果前面不存在s[k],那么此處為0,結(jié)果不變)

因?yàn)檫@兩種情況時(shí)分開討論的,不相交,因此當(dāng)s[i-1]==t[j-1]時(shí):

dp[i][j] = dp[i-1][j-1] + dp[i-1][j];

而當(dāng)s[i-1]!=t[j-1]時(shí):

我們考慮將s[i-1]刪除,因?yàn)椴幌嗟扔貌坏?/p>

但是不能刪除t[j-1],因?yàn)槲覀冊(cè)谇骴[i][j],j對(duì)應(yīng)的就是t[0,j-1],要是將t[j-1]去除,那就不能稱為dp[i][j]了(

因?yàn)閠是子串不能更改),所以不存在dp[i][j-1]和dp[i-1][j-1]兩種情況

因此轉(zhuǎn)移方程如下:

                if(s[i-1] == t[j-1])
                    dp[i][j] = dp[i-1][j-1] + dp[i-1][j];
                else{
                    dp[i][j] = dp[i-1][j];
                }

(3)初始化:

以樣例為參考:

代碼如下:

        vector<vector<unsigned long long>> dp(n+1,vector<unsigned long long>(m+1,0));
        for(int i = 0;i <= n;i++)
            dp[i][0] = 1;

(4)遍歷順序

兩層for循環(huán)即可

完整代碼如下:

class Solution {
public:
    int numDistinct(string s, string t) {
        int n = s.size(),m = t.size();
        vector<vector<unsigned long long>> dp(n+1,vector<unsigned long long>(m+1,0));
        for(int i = 0;i <= n;i++)
            dp[i][0] = 1;
        for(int i = 1;i <= n;i++)
            for(int j = 1;j <= m;j++){
                if(s[i-1] == t[j-1])
                    dp[i][j] = dp[i-1][j-1] + dp[i-1][j];
                else{
                    dp[i][j] = dp[i-1][j];
                }
                // dp[i][j] = dp[i][j] % (1000000007);
            }
        return dp[n][m];
    }
};

3.2.7 兩個(gè)字符串的刪除操作

編輯距離的簡(jiǎn)化版

(1) dp定義:
不要連續(xù)就,定義dp[i][j]表示word1[0,i-1],word2[0,j-1]的最小步數(shù)

(2)轉(zhuǎn)移方程

和編輯距離類似

word1[i-1] == word2[j-1]時(shí),不刪除,dp[i][j] = dp[i-1][j-1];

word1[i-1] != word2[j-1]時(shí),在三種刪除中選擇最小的

                if(word1[i-1] == word2[j-1])
                    dp[i][j] = dp[i-1][j-1];
                else{
                    dp[i][j] = min(
                        dp[i-1][j-1]+2,
                        dp[i-1][j]+1,
                        dp[i][j-1]+1
                    );

?(3)初始化

根據(jù)樣例進(jìn)行如下初始化:

代碼:

        vector<vector<int>> dp(n+1,vector<int>(m+1));
        
        for(int i = 0;i <= n;i++)dp[i][0] = i;
        for(int i = 0;i <= m;i++)dp[0][i] = i;

(4)遍歷順序?

完整代碼:

class Solution {
public:
    int min(int a,int b,int c){
        return std::min(std::min(a,b),c);
    }

    int minDistance(string word1, string word2){
        int n = word1.size(),m = word2.size();
        vector<vector<int>> dp(n+1,vector<int>(m+1));
        
        for(int i = 0;i <= n;i++)dp[i][0] = i;
        for(int i = 0;i <= m;i++)dp[0][i] = i;

        for(int i = 1;i <= n;i++)
            for(int j = 1 ;j <= m; j++){
                if(word1[i-1] == word2[j-1])
                    dp[i][j] = dp[i-1][j-1];
                else{
                    dp[i][j] = min(
                        dp[i-1][j-1]+2,
                        dp[i-1][j]+1,
                        dp[i][j-1]+1
                    );
                }
            }
        return dp[n][m];
    }
};

3.2.8 兩個(gè)字符串的最小ascii刪除和

?和上一題及其類似,只是初始化和更新轉(zhuǎn)移方程的形式有點(diǎn)區(qū)別,不多贅述

代碼如下:

class Solution {
public:

    int min(int a,int b,int c){
        return std::min(std::min(a,b),c);
    }

    int minimumDeleteSum(string s1, string s2){
        int n = s1.size(),m = s2.size();
        vector<vector<int>> dp(n+1,vector<int>(m+1));
        
        for(int i = 0;i <= n;i++)
            for(int j = 0;j < i;j++)
                dp[i][0] += int(s1[j]);
        for(int i = 0;i <= m;i++)
            for(int j = 0;j < i;j++)
                dp[0][i] += int(s2[j]);

        for(int i = 1;i <= n; i++)
            for(int j = 1 ;j <= m; j++){
                if(s1[i-1] == s2[j-1])
                    dp[i][j] = dp[i-1][j-1];
                else{
                    dp[i][j] = min(
                        dp[i-1][j-1]+int(s1[i-1])+int(s2[j-1]),
                        dp[i-1][j]+int(s1[i-1]),
                        dp[i][j-1]+int(s2[j-1])
                    );
                }
            }
        return dp[n][m];
    }
};

3.3 回文子串和子序列

(1)回文子串要求連續(xù),可以用雙指針進(jìn)行解答;

(2)但是回文子序列不連續(xù),雙指針失效,可以復(fù)制一份然后,將其倒轉(zhuǎn),使用雙序列的方法進(jìn)行解答.

3.3.1 回文子串

?

使用雙指針解法,相比dp解法時(shí)間復(fù)雜度更低?

代碼如下,細(xì)節(jié)參考數(shù)組一章,雙指針部分:

class Solution {
public:
    int jud(string s,int l,int r){
        int count = 0;
        while(l >=0 && r <s.size()&&s[l]==s[r]){
            l--;
            r++;
            count++;
        }
        return count;
    }
    int countSubstrings(string s){
        int count = 0;
        for(int i = 0;i < s.size();i++){
            count += jud(s,i,i);
            count += jud(s,i,i+1);
        }
        return count;
    }
};

3.3.2 最大回文子序列?

?將s復(fù)制一份再倒轉(zhuǎn),然后對(duì)兩個(gè)序列求最大公共子序列,代碼如下:文章來源地址http://www.zghlxwxcb.cn/news/detail-759184.html

//復(fù)制一份,倒轉(zhuǎn),求最大公共子序列
class Solution {
public:
    int longestPalindromeSubseq(string s) {
        string t = s;
        reverse(s.begin(),s.end());
        int n = s.size();
        vector<vector<int>> dp(n+1,vector<int>(n+1,0));
        for(int i = 1;i <= n;i++)
            for(int j = 1;j <= n;j++){
                if(s[i-1]==t[j-1])dp[i][j] = dp[i-1][j-1] + 1;
                else{
                    dp[i][j] = max(max(dp[i-1][j],dp[i][j-1]),dp[i-1][j-1]);
                }
            }
        return dp[n][n];
    }
};

到了這里，關(guān)于數(shù)據(jù)結(jié)構(gòu)與算法-動(dòng)態(tài)規(guī)劃的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！