每一種算法都最好看完第一篇再去找要看的博客，因?yàn)檫@樣會(huì)幫你梳理好思路，看接下來的博客也就更輕松了。當(dāng)然，我也會(huì)盡量在寫每一篇時(shí)都可以不懂這個(gè)算法的人也能邊看邊理解。

1、動(dòng)規(guī)思路簡介

動(dòng)規(guī)的思路有五個(gè)步驟，且最好畫圖來理解細(xì)節(jié)，不要怕麻煩。當(dāng)你開始畫圖，仔細(xì)閱讀題時(shí)，學(xué)習(xí)中的沉浸感就體驗(yàn)到了。

狀態(tài)表示
狀態(tài)轉(zhuǎn)移方程
初始化
填表順序
返回值

動(dòng)規(guī)一般會(huì)先創(chuàng)建一個(gè)數(shù)組，名字為dp，這個(gè)數(shù)組也叫dp表。通過一些操作，把dp表填滿，其中一個(gè)值就是答案。dp數(shù)組的每一個(gè)元素都表明一種狀態(tài)，我們的第一步就是先確定狀態(tài)。

狀態(tài)的確定可能通過題目要求來得知，可能通過經(jīng)驗(yàn) + 題目要求來得知，可能在分析過程中，發(fā)現(xiàn)的重復(fù)子問題來確定狀態(tài)。還有別的方法來確定狀態(tài)，但都大同小異，明白了動(dòng)規(guī)，這些思路也會(huì)隨之產(chǎn)生。狀態(tài)的確定就是打算讓dp[i]表示什么，這是最重要的一步。狀態(tài)表示通常用某個(gè)位置為結(jié)尾或者起點(diǎn)來確定，但兩個(gè)數(shù)組的問題則不是這樣，要選取第一個(gè)字符串[0, i]區(qū)間以及第二個(gè)字符串[0, j]區(qū)間作為研究對象。

狀態(tài)轉(zhuǎn)移方程，就是dp[i]等于什么，狀態(tài)轉(zhuǎn)移方程就是什么。像斐波那契數(shù)列，dp[i] = dp[i - 1] + dp[i - 2]。這是最難的一步。一開始，可能狀態(tài)表示不正確，但不要緊，大膽制定狀態(tài)，如果沒法推出轉(zhuǎn)移方程，沒法得到結(jié)果，那這個(gè)狀態(tài)表示就是錯(cuò)誤的。所以狀態(tài)表示和狀態(tài)轉(zhuǎn)移方程是相輔相成的，可以幫你檢查自己的思路。

要確定方程，就從最近的一步來劃分問題。

初始化，就是要填表，保證其不越界。像第一段所說，動(dòng)規(guī)就是要填表。比如斐波那契數(shù)列，如果要填dp[1]，那么我們可能需要dp[0]和dp[-1]，這就出現(xiàn)越界了，所以為了防止越界，一開始就固定好前兩個(gè)值，那么第三個(gè)值就是前兩個(gè)值之和，也不會(huì)出現(xiàn)越界。初始化的方式不止這一點(diǎn)，有些問題，假使一個(gè)位置是由前面2個(gè)位置得到的，我們初始化最一開始兩個(gè)位置，然后寫代碼，會(huì)發(fā)現(xiàn)不夠高效，這時(shí)候就需要設(shè)置一個(gè)虛擬節(jié)點(diǎn)，一維數(shù)組的話就是在數(shù)組0位置處左邊再填一個(gè)位置，整個(gè)dp數(shù)組的元素個(gè)數(shù)也+1，讓原先的dp[0]變?yōu)楝F(xiàn)在的dp[1]，二維數(shù)組則是要填一列和一行，設(shè)置好這一行一列的所有值，原先數(shù)組的第一列第一行就可以通過新填的來初始化，這個(gè)初始化方法在下面的題解中慢慢領(lǐng)會(huì)。

第二種初始化方法的注意事項(xiàng)就是如何初始化虛擬節(jié)點(diǎn)的數(shù)值來保證填表的結(jié)果是正確的，以及新表和舊表的映射關(guān)系的維護(hù)，也就是下標(biāo)的變化。

填表順序。填當(dāng)前狀態(tài)的時(shí)候，所需要的狀態(tài)應(yīng)當(dāng)已經(jīng)計(jì)算過了。還是斐波那契數(shù)列，填dp[4]的時(shí)候，dp[3]和dp[2]應(yīng)當(dāng)都已經(jīng)計(jì)算好了，那么dp[4]也就出來了，此時(shí)的順序就是從左到右。還有別的順序，要依據(jù)前面的分析來決定。

返回值，要看題目要求。

這篇博客需要從頭開始看，后面的題會(huì)用到前面的思路。

2、最長公共子序列

1143. 最長公共子序列

確定狀態(tài)。讓dp[i][j]表示s1的[0, i]區(qū)間以及s2的[0, j]區(qū)間內(nèi)所有的子序列中，最長公共子序列的長度。

如果s1和s2最后一個(gè)字符相同，那么最長公共子序列一定是以這個(gè)字符為結(jié)尾的。如果公共子序列在s1和s2內(nèi)部，那么再連接最后一個(gè)字符才是最長公共子序列；如果s1的公共子序列從某個(gè)字符到最后一個(gè)字符，而s2的公共序列在內(nèi)部，那么既然是公共序列，最后一個(gè)字符一定相同，那么s2就可以連接最后一個(gè)字符。

i和j從字符串的末尾開始，如果s[i] == s[j]，那么只需要在0 ~ i - 1和0 ~ j - 1找到公共子序列，然后+1就可。如果s[i] != s[j]，那么最長公共子序列一定不以這兩個(gè)字符結(jié)尾，這樣的話我們就可以在s1的[0, i - 1]和s2的[0, j]里找公共子序列，或者[0, i]，[0, j - 1]，或者[0, i - 1]和[0, j - 1]，也就是3種情況，實(shí)際上前兩個(gè)包含最后一個(gè)情況[0, i - 1]，[0, j - 1]，但不干擾最后最后結(jié)果，因?yàn)槲覀円氖亲铋L長度，重復(fù)的問題不需要考慮，只要能保證不漏掉情況就行，只是還是可以優(yōu)化，就不去考慮第三種情況。如果題目要求求最長公共子序列個(gè)數(shù)，那么第3種情況肯定要去掉，因?yàn)橐呀?jīng)包含了。

初始化?？沾怯醒芯恳饬x的，因?yàn)榭沾彩枪沧有蛄?，只是長度為0，并且因?yàn)榭沾拇嬖?，也方便初始化?二維數(shù)組dp表，多添加一行一列，讓原先的[0][0]變成現(xiàn)在的[1][1]，現(xiàn)在的第一行表示s1為空的情況，第一列表示s2為空的情況。為了保證添加的一行一列的值保證后續(xù)填表是正確的，以及下標(biāo)的映射關(guān)系，我們對于字符串可以在最前面加個(gè)空字符就行。

填表順序，因?yàn)樾枰猧 - 1，j - 1，所以從上到下，每一行從左到右。返回值是最大值，也就是dp表右下角的值。

    int longestCommonSubsequence(string s1, string s2) {
        int m = s1.size(), n = s2.size();
        s1 = " " + s1, s2 = " " + s2;
        vector<vector<int>> dp(m + 1, vector<int>(n + 1));
        for(int i = 1; i <= m; i++)
        {
            for(int j = 1; j <= n; j++)
            {
                if(s1[i] == s2[j]) dp[i][j] = dp[i - 1][j - 1] + 1;//如果前面沒有加那個(gè)空字符，那么這里就得些s1[i - 1] == s2[j - 1]，保證下標(biāo)對齊
                else dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
            }
        }
        return dp[m][n];
    }

3、不相交的線

1035. 不相交的線

這道題建立在公共子序列的思路基礎(chǔ)上。不交叉的線，也就是上面選中的數(shù)字的順序，下面選中的數(shù)字也得按照這個(gè)順序選中，這樣就可以保證符合要求。其實(shí)這就是在找公共子序列的問題，序列中的元素可以不連續(xù)，但順序不會(huì)變，左邊的元素都比右邊元素靠前，所以這道題就轉(zhuǎn)化為了最長公共子序列的長度。

定義dp[i][j]為nums1里的[0, i]區(qū)間以及nums2里的[0, j]區(qū)間里面的所有的子序列中，最長公共子序列的長度，因?yàn)轭}目要求求長度。按照公共子序列的思路，可以分為兩種情況，n1[i] == n2[j]，兩個(gè)數(shù)字相等，那就找dp[i - 1][j - 1]，因?yàn)檫@里存的是n1到第i - 1個(gè)數(shù)字，n2到第j - 1個(gè)數(shù)字的最長的公共子序列，然后 + 1就是dp[i][j]應(yīng)當(dāng)存的值。如果n1[i] != n2[j]，那么就轉(zhuǎn)換為三種情況，找到do[i - 1][j]，dp[i][j - 1]，dp[i - 1][j - 1]的最大值當(dāng)作dp[i][j]的值，因?yàn)榍皟蓚€(gè)包含了dp[i - 1][j - 1]的情況，所以只考慮前兩個(gè)。這樣dp表的填寫就完成了。

由于我們需要i - 1，j - 1，所以在原本的dp表左上角加上一行一列，里面的數(shù)字要保證不影響后續(xù)的填表以及下標(biāo)的映射關(guān)系，之前[0, 0]變成了[1, 1]，所以新增的行列里的值都變成0，因?yàn)槲覀円∽畲笾?，所以這樣就不影響。填表順序是從上到下，從左到右。返回值是dp[n1][n2]。

    int maxUncrossedLines(vector<int>& nums1, vector<int>& nums2) {
        int m = nums1.size(), n = nums2.size();
        vector<vector<int>> dp(m + 1, vector<int>(n + 1));
        for(int i = 1; i <= m; i++)
        {
            for(int j = 1; j <= n; j++)
            {
                if(nums1[i - 1] == nums2[j - 1]) dp[i][j] = dp[i - 1][j - 1] + 1;
                else dp[i][j] = max(dp[i][j - 1], dp[i - 1][j]);
            }
        }
        return dp[m][n];
    }

4、不同的子序列

115. 不同的子序列

根據(jù)題目要求，得在s中找t。由于是子序列，所以不必讓t完整地出現(xiàn)，看看示例就明白了。既然是子序列，按照之前的思路，我們還是得看看最后一個(gè)元素的情況，以及需要用到dp表中前面的值。

先定義dp[i][j]表示s的[0, j]區(qū)間內(nèi)的所有子序列中，有多少個(gè)t的[0, i]區(qū)間內(nèi)的子串。注意一個(gè)是子序列，一個(gè)是子串，這兩個(gè)的含義需要分清，一個(gè)不需要連續(xù)，一個(gè)必須連續(xù)的字符。接下來確定狀態(tài)轉(zhuǎn)移方程。s的子序列中有兩個(gè)情況，包含s[j]和不包含。如果包含s[j]，要是想包含t[0, i]區(qū)間的子串，就得讓s[j] == t[i]才可行，這兩個(gè)字符相等了，那就再找dp[i - 1][j - 1]，不需要 + 1，因?yàn)榍蟮氖莻€(gè)數(shù)，不是長度。如果不包含s[j]，那么就往前一步，變成[0, j - 1]里找t，也就是dp[i][j - 1]。因?yàn)檎业氖莻€(gè)數(shù)，所以dp[i][j] = dp[i][j - 1] + dp[i - 1][j - 1]。

初始化的時(shí)候，因?yàn)橛衖 - 1和j - 1，新增一行列比較好，新增在左上角。第一行，代表dp[0][j]，也就是說t是空串，那么這一行應(yīng)當(dāng)都初始化為1，因?yàn)榭隙ò沾?；第一列，dp[i][0]，s是空串，那么就不包含t了，應(yīng)當(dāng)初始化為0，而dp[0][0]這個(gè)位置，兩個(gè)都是空串，應(yīng)當(dāng)為1，這點(diǎn)在上面初始化第一行時(shí)就做好了。填表順序是從上到下，從左到右。返回值就是dp[m][n]。

    int numDistinct(string s, string t) {
        int m = t.size(), n = s.size();
        vector<vector<double>> dp(m + 1, vector<double>(n + 1));//long和long long都不行，溢出
        for(int j = 0; j <= n; j++) dp[0][j] = 1;
        for(int i = 1; i <= m; i++)
        {
            for(int j = 1; j <= n; j++)
            {
                dp[i][j] += dp[i][j - 1];
                if(t[i - 1] == s[j - 1]) dp[i][j] += dp[i - 1][j - 1];
            }
        }
        return dp[m][n];
    }

5、通配符匹配

44. 通配符匹配

像abcde和ae這樣，星號匹配空字符，星號匹配bcd都是可以的。

根據(jù)經(jīng)驗(yàn)，兩個(gè)字符串分別選取[0, i]和[0, j]區(qū)間。題目中是能否匹配成功，那么我們就定義dp[i][j]是p[0, j]區(qū)間的子串能否匹配s[0, i]區(qū)間內(nèi)的子串，類型是bool。

狀態(tài)轉(zhuǎn)移方程。還是根據(jù)最后一個(gè)位置的狀況來確定問題。因?yàn)槭峭ㄅ浞?，每個(gè)位置都有三種情況。如果最后一個(gè)位置是普通字符，那么如果p[j] == s[i]，就看dp[i - 1][j - 1]是否為true；如果最后一個(gè)位置是?，它可以直接匹配一個(gè)字符，然后再看dp[i - 1]
[j - 1]；如果最后一個(gè)位置是星號，星號可以匹配很多種，匹配空字符，就看dp[i][j - 1]，匹配1個(gè)字符，就看dp[i - 1][j - 1]，匹配2個(gè)字符，就看dp[i - 2][j - 1]。星號的情況如何實(shí)現(xiàn)到代碼上？dp[i][j] = dp[i - 0][j - 1] || dp[i - 1][j - 1] || dp[i - 2][j - 1]，如果i變?yōu)閕 - 1，那么dp[i - 1][j] = dp[i - 1][j - 1] || dp[i - 2][j - 1] || dp[i - 3][j - 1]，所以可以發(fā)現(xiàn)dp[i][j]就等于dp[i][j - 1] || dp[i - 1][j]，后面的所有情況都包含在dp[i - 1][j]中。

初始化，因?yàn)橛衖 - 1，j - 1，我們就需要在左上角新增一行一列。新增行列的初始化需要做一下分析，第一個(gè)位置dp[0][0]，空串匹配空串，這肯定是true；第一列表示dp[i][0]，p是空串，那它不能匹配字符串，所以第一列除了第一個(gè)元素，其它都是false；第一行，也就是dp[0][j]，s是空串，p只有是星號才能是true，不是的話就是false。下標(biāo)映射關(guān)系也需要分析一下，我們可以按照之前的做法，下標(biāo)減1，而因?yàn)槭亲址?，也可以在字符串之前加一個(gè)空字符。

填表順序是從上到下，從左到右。返回值就是右下角那個(gè)值。

    bool isMatch(string s, string p) {
        int m = s.size(), n = p.size();
        vector<vector<bool>> dp(m + 1, vector<bool>(n + 1));
        s = " " + s, p = " " + p;
        dp[0][0] = true;
        for(int j = 1; j <= n; j++)
        {
            if(p[j] == '*') dp[0][j] = true;
            else break;
        }
        for(int i = 1; i <= m; i++)
        {
            for(int j = 1; j <= n; j++)
            {
                if(p[j] == '*') dp[i][j] = dp[i - 1][j] || dp[i][j - 1];
                else dp[i][j] = (p[j] == '?' || s[i] == p[j]) && dp[i - 1][j - 1];
            }
        }
        return dp[m][n];
    }

6、正則表達(dá)式匹配

10. 正則表達(dá)式匹配

這里的星號和上一個(gè)題不一樣，星號不能連續(xù)，任意一個(gè)字符搭配星號可以變成空串。還是選取s[0, i]區(qū)間，p[0, j]區(qū)間。dp[i[j]表示p[0, j]區(qū)間內(nèi)的子串是否能夠匹配s[o, i]區(qū)間內(nèi)的子串，所以是bool。

狀態(tài)轉(zhuǎn)移方程。還是根據(jù)最后一個(gè)位置的狀態(tài)來分析。先看最后一個(gè)位置，如果p[j] == s[i]，那就看dp[i - 1][j - 1]是否為true，那么dp[i][j]就是true；如果p[j]是點(diǎn)號，那肯定沒問題；如果是星號，它得看前面一個(gè)值，前面是點(diǎn)號，那么這兩個(gè)字符可以轉(zhuǎn)換成0個(gè)以及多個(gè)點(diǎn)號，空串就得看dp[i][j - 2]，一個(gè)點(diǎn)號就看dp[i - 1][j - 2]，轉(zhuǎn)換成2個(gè)點(diǎn)號就是dp[i - 2][j - 2]，以此類推，只要有一個(gè)為true，那么dp[i][j]就是true，dp[i][j]是這樣，那么dp[i - 1][i]也能表示出來，所以最后能得到dp[i][j] = dp[i][j - 2] || dp[i - 1][j]。如果p[j]是星號，p[j - 1]是普通字符，那么有兩種情況，可以匹配成空串，那就看dp[i][j - 2]，如果匹配一個(gè)，也就是p[j - 1]和s[i]相等的話，再就看dp[i - 1][j]是否為true。

所以方程應(yīng)當(dāng)是這樣的：p[j] == s[i]或者p[j]是一個(gè)點(diǎn)，那就看dp[i - 1][j - 1]是否true，dp[i][j]才為true。如果p[j]是星號，有兩種大情況，每個(gè)情況都有匹配成空串的情況，都是dp[i][j - 2]，以及還要看是點(diǎn)還是普通字符，再看dp[i - 1][j]。

初始化時(shí)最前面引入空串，新增行列，管理好下標(biāo)的映射關(guān)系。dp[0][0]是true，第一列其余部分就是false，因?yàn)榈谝涣斜硎緋是空串，這肯定不能匹配；第一行是s為空串，p可以任意一個(gè)字符搭配星號，多個(gè)這樣的組合也行，只要偶數(shù)位置是星號就行。

填表順序是從上到下，從左到右。返回值是dp[m][n]。

    bool isMatch(string s, string p) {
        int m = s.size(), n = p.size();
        vector<vector<bool>> dp(m + 1, vector<bool>(n + 1));
        s = ' ' + s, p = ' ' + p;
        dp[0][0] = true;
        for(int j = 2; j <= n; j += 2)
        {
            if(p[j] == '*') dp[0][j] = true;
            else break;
        }
        for(int i = 1; i <= m; i++)
        {
            for(int j = 1; j <= n; j++)
            {
                if(p[j] == '*') 
                    dp[i][j] = dp[i][j - 2] || (p[j - 1] == '.' || p[j - 1] == s[i]) && dp[i - 1][j];
                else dp[i][j] = (p[j] == s[i] || p[j] == '.') && dp[i - 1][j - 1];
            }
        }
        return dp[m][n];
    }

7、交錯(cuò)字符串

97. 交錯(cuò)字符串

s3是由s1和s2中的序列構(gòu)成的，長度等于這兩個(gè)字符串之和。為了能讓分析更清楚，三個(gè)字符串前面都加上一個(gè)空字符，這樣就是s1[1, i]，s2[1, j]，s3[1, i+j]區(qū)間做分析。

把dp[i][j]表示為s1[1, i]區(qū)間內(nèi)的字符串以及s2[1, j]區(qū)間內(nèi)的字符串能否拼接湊成s3[1, i+j]區(qū)間內(nèi)的字符串，類型就是bool。

狀態(tài)轉(zhuǎn)移方程。根據(jù)最后一個(gè)位置來分析。如果s3[i + j]處的結(jié)尾字符有可能是s1的，也有可能是s2的，所以分為兩種情況，如果是s1，如果s1[i] == s3[i + j]，那么就看dp[i - 1][j]是否為true，s2也同理，看dp[i][j - 1]是否為true。

初始化時(shí)，在左上角新增一行一列，dp[0][0]，也就是3個(gè)字符串都為0，就是true。第一列，也就是s2為空時(shí)，dp[i][0]，就看s1和s3之間哪個(gè)位置字符相同，哪個(gè)就是true，不是就之后所有位置都是false；第一行也是如此，比較s2和s3。填表順序是從上到下，從左到右。返回值是dp[m][n]。

    bool isInterleave(string s1, string s2, string s3) {
        int m = s1.size(), n = s2.size();
        if(m + n != s3.size()) return false;
        s1 = ' ' + s1, s2 = ' ' + s2, s3 = ' ' + s3;
        vector<vector<bool>> dp(m + 1, vector<bool>(n + 1));
        dp[0][0] = true;
        for(int j = 1; j <= n; j++)
        {
            if(s2[j] == s3[j]) dp[0][j] = true;
            else break;
        }
        for(int i = 1; i <= m; i++)
        {
            if(s1[i] == s3[i]) dp[i][0] = true;
            else break;
        }
        for(int i = 1; i <= m; i++)
        {
            for(int j = 1; j <= n; j++)
            {
                dp[i][j] = (s1[i] == s3[i + j] && dp[i - 1][j]) || (s2[j] == s3[i + j] && dp[i][j - 1]);
            }
        }
        return dp[m][n];
    }

8、兩個(gè)字符串的最小ASCII刪除和

712. 兩個(gè)字符串的最小ASCII刪除和

仔細(xì)分析示例會(huì)發(fā)現(xiàn)，兩個(gè)字符串有多種刪除法，得到不同的結(jié)果字符串，但是刪除的字符的ASCII碼值最小的結(jié)果，是s1和s2中的公共子序列，并且還是ASCII值最大的那個(gè)，所以這個(gè)問題就變成了找公共子序列中ASCII值最大的。

讓dp[i][j]表示s1的[0, i]區(qū)間以及s2的[0, j]區(qū)間內(nèi)的所有的子序列里，公共子序列的ASCII最大和。

狀態(tài)轉(zhuǎn)移方程。看最后一個(gè)位置來分析，如果s[i] == s[j]，那么就看dp[i - 1][j - 1]，然后再加上這個(gè)位置的值即可；如果不相等，那么就變成兩種情況，s1以i - 1位置結(jié)尾來分析dp[i - 1][j]和s2以j - 1位置為結(jié)尾來分析dp[i][j - 1]。

初始化時(shí)，左上角新增一行一列，要管理好下標(biāo)的映射關(guān)系，新增行列初始化為0。

填表順序是從上到下，從左到右。最大值是dp[m][n]，然后用2個(gè)字符串的ASCII和來減去兩倍的dp[m][n]，因?yàn)閮蓚€(gè)字符串都要減。

   int minimumDeleteSum(string s1, string s2) {
        int m = s1.size(), n = s2.size();
        vector<vector<int>> dp(m + 1, vector<int>(n + 1));
        for(int i = 1; i <= m ; i++)
        {
            for(int j = 1; j <= n; j++)
            {
                dp[i][j] = max(dp[i][j - 1], dp[i - 1][j]);
                if(s1[i - 1] == s2[j - 1])
                    dp[i][j] = max(dp[i][j], dp[i - 1][j - 1] + s1[i - 1]);
            }
        }
        int sum = 0;
        for(auto s : s1) sum += s;
        for(auto s : s2) sum += s;
        return sum - (2 * dp[m][n]);
    }

9、最長重復(fù)子數(shù)組

718. 最長重復(fù)子數(shù)組

如果以[0, i]區(qū)間來分析，找子數(shù)組，這個(gè)角度就不行，因?yàn)樽訑?shù)組和子序列不同，它必須是連續(xù)的，[0, i]區(qū)間內(nèi)的最長子數(shù)組可能不以i結(jié)尾，而是以前面的某個(gè)位置結(jié)尾，所以就無法確定最長長度。這題的狀態(tài)表示應(yīng)當(dāng)改為dp[i][j]是nums1中以i位置元素為結(jié)尾的所有子數(shù)組和nums2中以j位置元素為結(jié)尾的所有子數(shù)組中最長重復(fù)子數(shù)組的長度。

狀態(tài)轉(zhuǎn)移方程。以最后一個(gè)位置來分析。如果nums1[i] != nums[j]，那此時(shí)就不是重復(fù)的子數(shù)組，如果相等的話，結(jié)尾位置就沒問題了，那就再看前面一個(gè)位置，所以應(yīng)當(dāng)是dp[i - 1][j - 1] + 1。

初始化時(shí)，新增一行一列，注意下標(biāo)的映射關(guān)系，新增的行列應(yīng)當(dāng)全為0。

填表順序是從上到下，從左到右。返回值是最大值。

    int findLength(vector<int>& nums1, vector<int>& nums2) {
        int m = nums1.size(), n = nums2.size();
        vector<vector<int>> dp(m + 1, vector<int>(n + 1));
        int ret = 0;
        for(int i = 1; i <= m; i++)
        {
            for(int j = 1; j<= n; j++)
            {
                if(nums1[i - 1] == nums2[j - 1])
                {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                    ret = max(ret, dp[i][j]);
                }
            }
        }
        return ret;
    }

結(jié)束。文章來源地址http://www.zghlxwxcb.cn/news/detail-729321.html

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