前言

動(dòng)態(tài)規(guī)劃往期文章:

1. 動(dòng)態(tài)規(guī)劃入門：斐波那契數(shù)列模型以及多狀態(tài)
2. 動(dòng)態(tài)規(guī)劃：路徑和子數(shù)組問題
3. 動(dòng)態(tài)規(guī)劃：子序列問題
4. 動(dòng)態(tài)規(guī)劃：回文串問題

兩個(gè)數(shù)組的dp問題

1.最長公共子序列（中等）

鏈接：最長公共子序列

• 題目描述
  

• 做題步驟

1. 狀態(tài)表示
   對(duì)于兩個(gè)數(shù)組的dp，采用一維dp是沒有辦法清晰的表示狀態(tài)的，故對(duì)于兩個(gè)數(shù)組的dp我們通常采用二維數(shù)組。
   
   故定義狀態(tài)表示為dp[i] [j]：s1的[0，i]區(qū)間和s2的[0，j]區(qū)間之間的最長公共子序列。

2. 狀態(tài)轉(zhuǎn)移方程
   對(duì)s1的[0，i]區(qū)間和s2的[0，j]區(qū)間，我們分情況討論：
   (1)s1[i] == s2[j]，我們只需要知道s1的[0，i - 1]區(qū)間和s2的[0，j - 1]區(qū)間之間的最長公共子序列，然后加一即可，即dp[i] [j] = dp[i - 1] [j - 1] + 1。（比如s1 = "abc"和s2 = “akc”，就是"ab"和"ak"的最長公共子序列加1）
   
   (2)s1[i] != s2[j]，這個(gè)這時(shí)最長公共子序列?定不會(huì)同時(shí)以s1[i]和s2[j]結(jié)尾。
   ①有可能以s2[j]結(jié)尾，去s1的 [0, i - 1]以及s2的 [0, j] 區(qū)間內(nèi)找：此時(shí)最大長度為dp[i - 1] [j]。（比如s1 = “ack”，s2 = “bc”）
   ②有可能以s1[i]結(jié)尾，去s1的[0, i]以及s2的 [0, j - 1] 區(qū)間內(nèi)找：此時(shí)最大長度為dp[i] [j - 1]。（比如s1 = “ac”，s2 = “cb”）
   ③也有可能兩者都不是結(jié)尾，但這個(gè)情況是包括在前兩個(gè)情況中的，一定小于等于前兩者。（比如s1 = “acd”，s2 = “aca”）
   故對(duì)于(2)情況，dp[i] [j] = max(dp[i - 1] [j], dp[i] [j - 1])。

3. 初始化

4. 填表順序
   參照上面的圖，填表順序?yàn)?font color="red">行從上到下，每一行從左到右。

5. 返回值
   依據(jù)狀態(tài)表示，返回值為dp[m] [n]（m，n分別為s1、s2長度）。

• 代碼實(shí)現(xiàn)

class Solution {
public:
    int longestCommonSubsequence(string s1, string s2) {
        int m = s1.size(), n = s2.size();
        vector<vector<int>> dp(m + 1, vector<int>(n + 1));
        //處理下標(biāo)映射
        s1 = " " + s1, s2 = " " + s2;
        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;         
                else
                    dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);               
            }     
        return dp[m][n];
    }
};

2.不同的子序列（困難）

鏈接：不同的子序列

• 題目描述
  

• 做題步驟

1. 狀態(tài)表示
   這個(gè)題目雖然標(biāo)的是困難，但是有前面的做題經(jīng)驗(yàn)其實(shí)還好。
   對(duì)這種問題，我們采用二維表，定義狀態(tài)表示為dp[i] [j]：t的[0, j]區(qū)間在s的[0, i]區(qū)間出現(xiàn)的方案個(gè)數(shù)。

2. 狀態(tài)轉(zhuǎn)移方程
   對(duì)s的[0，i]區(qū)間和t的[0，j]區(qū)間，我們分情況討論：
   (1)s[i] == t[j]：
   ①比如t = "rab"和s = “rabcb”,第一種同時(shí)選s[i]、t[j]為結(jié)尾，這個(gè)時(shí)候的方案數(shù)為t的[0, j - 1]區(qū)間在s的[0, i - 1]區(qū)間出現(xiàn)的方案數(shù)(ra在rabc中出現(xiàn)的次數(shù))，即dp[i - 1] [j - 1]。
   ②第二種是不同時(shí)選s[i]、t[j]為結(jié)尾，這個(gè)時(shí)候的方案數(shù)為t的[0, j]區(qū)間在s的[0, i - 1]區(qū)間出現(xiàn)的方案數(shù)(t = "rab"在s的"rabc"中出現(xiàn)的次數(shù))，即dp[i - 1] [j]。
   兩種都符合要求：故(1)情況dp[i] [j] = dp[i - 1] [j] + dp[i - 1] [j - 1]
   
   (2)s[i] != t[j]：
   這個(gè)時(shí)候只有一種選擇，即(1)的②情況，故(2)情況dp[i] [j] = dp[i - 1] [j] 。

3. 初始化
   這個(gè)題目的初始化和上一題相似，多開一行一列，把多的一行一列當(dāng)作空串。其中當(dāng)t為空串時(shí)在s中一定有一種方案（s也拿一個(gè)空串出來），故初始化第一列為1。

4. 填表順序
   填表不明白參考第一題，填表順序?yàn)?font color="red">行從上到下，每一行從左到右。

5. 返回值
   依據(jù)狀態(tài)表示，返回值為dp[m] [n]（m，n分別為s、t長度）。

• 代碼實(shí)現(xiàn)

class Solution {
public:
    int numDistinct(string s, string t) {
        int m = s.size(), n = t.size();
        //這個(gè)題目中間填表的時(shí)候會(huì)溢出，而且溢的不是一點(diǎn)點(diǎn)
        //不過溢出的部分不影響結(jié)果，用uint即可
        vector<vector<unsigned int>> dp(m + 1, vector<unsigned int>(n + 1));
        s = " " + s, t =  " " + t;  //處理下標(biāo)映射
        for(int i = 0; i < m; i++)  dp[i][0] = 1;
        for(int i = 1; i <= m; i++)
            for(int j = 1; j <= n; j++)
            {
                dp[i][j] = dp[i - 1][j];
                if(s[i] == t[j])  //s[i] == t[j]會(huì)多一種選擇
                    dp[i][j] += dp[i - 1][j - 1];                         
            }
        return dp[m][n];
    }
};

3.通配符匹配（困難）

鏈接：通配符匹配

• 題目描述
  

• 做題步驟

1. 狀態(tài)表示
   依據(jù)前面的做題經(jīng)驗(yàn)，我們定義一個(gè)二維表，定義狀態(tài)表示為dp[i] [j]：p的[0, j]區(qū)間能否匹配s的[0, i]區(qū)間。

2. 狀態(tài)轉(zhuǎn)移方程
   對(duì)s的[0，i]區(qū)間和p的[0，j]區(qū)間，我們分情況討論：
   (1)s[i] == p[j]或者p[j] == '?'時(shí)，dp[i] [j] = dp[i - 1] [j - 1]，即只要p的[j - 1]區(qū)域能和s的[i - 1]區(qū)域匹配，p的[0, j]就可以和s的[0, i]匹配。（比如s = “abc”，p = “ab?”）
   
   (2)p[j] == ’ * ’ 的情況，這個(gè)時(shí)候有三種可能使得p[0, j]和s[0, i]匹配：
   ①p的[0, j]可以和s的[0, i - 1]匹配，p[j] == ’ * ’ 在表示原來的字符串基礎(chǔ)上加上s[i]即可，即dp[i - 1] [j]為真dp[i] [j]為真。（比如s = “abc”，p = “a*”，"ab"和"a*"是匹配的）
   ②p的[0, j - 1]可以和s的[0, i]匹配， ’ * ’ 這個(gè)時(shí)候匹配空串即可，即dp[i] [j - 1]為真dp[i] [j]為真。（比如s = “ab”，p = “ab*”）
   ③p[0, j - 1]匹配和s的[0, i - 1]，p[j] == ’ * ’ 去替換s[i]，但這種情況實(shí)際是可以被歸于第一種情況的，如果s[0, i - 1]和p[0, j - 1]匹配，那么s[0, i - 1]和p[0 , j]也一定會(huì)匹配，這個(gè)時(shí)候 ’ * ’ 做空字符串，即dp[i - 1] [j - 1]為真 == dp[i - 1] [j]為真。
   
   以上情況只要一個(gè)為真dp[i] [j]就為真。

3. 初始化
   和前面一樣，為了避免越界以及方便初始化，我們引入空串的概念，多開一行和一列。
   ①其中兩者都為空串可匹配，即dp[0] [0] = true。
   
   ②s為空串，p不為空串(第一行除去[0, 0])的時(shí)候如果p的[0, j]區(qū)間為連續(xù)的 ’ * ’ 也是可以匹配空串的，dp[0] [0……j] = true。([0, j]區(qū)間表示連續(xù)的 ’ * ’ )
   
   ③p為空串，s不為空串(第一列除去[0, 0])，這個(gè)時(shí)候不可能匹配，第一列除開[0][0]其它都初始化為false。

4. 填表順序
   填表不明白參考第一題，填表順序?yàn)?font color="red">行從上到下，每一行從左到右。

5. 返回值
   依據(jù)狀態(tài)表示，返回值為dp[m] [n]（m，n分別為s、p長度）。

• 代碼實(shí)現(xiàn)

class Solution {
public:
    bool isMatch(string s, string p) {
        int m = s.size(), n = p.size();
        s = " " + s, p = " " + p;   //處理下標(biāo)映射
        //dp[i][j]：p的[0, j]區(qū)間能否匹配s的[0, i]區(qū)間
        vector<vector<bool>> dp(m + 1, vector<bool>(n + 1));
        dp[0][0] = true;  
        for(int j = 1; j <=n; j++)  //初始化s為空串，p有連續(xù)'*'可匹配的情況
        {
            if(p[j] == '*')
                dp[0][j] = true;
            else
                break;  //出現(xiàn)非'*'直接結(jié)束循環(huán)，后面不可能匹配了
        }
        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 if(s[i] == p[j] || p[j] == '?')
                    dp[i][j] = dp[i - 1][j - 1];
            }
        return dp[m][n];
    }
};

4.正則表達(dá)式（困難）

鏈接：正則表達(dá)式

• 題目描述
  

• 做題步驟

1. 狀態(tài)表示
   有前面的做題經(jīng)驗(yàn)，我們定義一個(gè)二維表，定義狀態(tài)表示為dp[i] [j]：p的[0, j]區(qū)域能否匹配s的[0, i]區(qū)域。

2. 狀態(tài)轉(zhuǎn)移方程
   這個(gè)題目的重點(diǎn)："a*"說明這個(gè)部分可以出現(xiàn)多次，也可以出現(xiàn)0次，即a表示空串，所以分析的時(shí)候應(yīng)該把"字符 + "當(dāng)作一個(gè)整體來考慮。
   
   對(duì)s的[0，i]區(qū)間和p的[0，j]區(qū)間，我們分情況討論：
   (1)s[i] == p[j]或p[j] == ’ . ’ ，只需要p的[0, j - 1]和s的[0, i - 1]匹配即可，即dp[i - 1] [j - 1]為真dp[i] [j]就為真。（比如s = "abc"和p = “ab.”）
   
   (2)p[j] == ’ * ’ 的情況，這個(gè)時(shí)候有三種可能使得p[0, j]和s[0, i]匹配：
   ①p[0, j - 2]和s[0, i]匹配，后面的"字符+"表示空串。即dp[i] [j - 2]為真dp[i] [j]就為真。（比如s = “abc”，p = “abcg*”，p后面的"g*"可以直接作空串）
   ②p[0, j]和s[0, i - 1]匹配，原本的"字符+"需要多表示一個(gè)字符。
   但這里多表示的字符是固定的，也就是說必須滿足p[j - 1] == s[i] 或 p[j - 1] == ’ . ’ ，這個(gè)多表示的字符才能符合要求。即滿足前面條件dp[i - 1] [j]為真dp[i] [j]就為真。
   （比如s = “abbb”，p = “ab*”，其中"ab*"是可以匹配"abb"的，剛好"b*"多表示一個(gè)’ b ’ 符合匹配要求。如果s = "abbc"就p就無法匹配s了）
   
   以上情況只要一個(gè)為真dp[i] [j]就為真。

3. 初始化
   為了避免越界已經(jīng)方便初始化，我們引入空串的概念，多開一行一列。
   ①其中兩者都為空串可匹配，即dp[0] [0] = true。
   
   ②當(dāng)s為空串，p不為空串(第一行除去[0, 0])的時(shí)候如果p為連續(xù)的"字符 + * + 字符 + * ……"，讓這些"字符+ *"全都作空串，是可以匹配s的。即dp[0] [j] = true(j = 2; j <= n; j += 2)。
   
   ③p為空串，s不為空串(第一列除去[0, 0])，這個(gè)時(shí)候不可能匹配，第一列除開[0] [0]其它都初始化為false。

4. 填表順序
   填表不明白參考第一題，填表順序?yàn)?font color="red">行從上到下，每一行從左到右。

5. 返回值
   依據(jù)狀態(tài)表示，返回值為dp[m] [n]（m，n分別為s、p長度）。

• 代碼實(shí)現(xiàn)

class Solution {
public:
    bool isMatch(string s, string p) {
        int m = s.size(), n = p.size();
        //處理下標(biāo)映射
        s = " " + s,  p = " " + p;
        //dp[i][j]：p的[0,j]區(qū)域能否和s的[0,i]區(qū)域匹配
        vector<vector<bool>> dp(m + 1, vector<bool>(n + 1));
        dp[0][0] = 1;  //空串可以匹配空串
        for(int j = 2; j <= n; j += 2)  //s為空串時(shí)p為連續(xù)的"字符 + *"是可以匹配的
        {
            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 if(s[i] == p[j] || p[j] == '.')
                {
                    dp[i][j] = dp[i - 1][j - 1];
                }
            }
        return dp[m][n];
    }
};

5.交錯(cuò)字符串（中等）

鏈接：交錯(cuò)字符串

• 題目描述
  

• 做題步驟

1. 狀態(tài)表示
   有前面的做題經(jīng)驗(yàn)，我們定義一個(gè)二維表，定義狀態(tài)表示為dp[i] [j]：s1的[0, i]區(qū)間和s2的[0, j]區(qū)間能否交錯(cuò)組成s3的[0, i + j]區(qū)間。

2. 狀態(tài)轉(zhuǎn)移方程
   對(duì)s1的[0，i]區(qū)間和s2的[0，j]區(qū)間能否交錯(cuò)組成s3的[0, i + j]區(qū)間，我們分情況討論：
   (1)s1[i] == s3[i + j]。這個(gè)時(shí)候只要s1的[0, i - 1]區(qū)間和s2的[0, j]區(qū)間可以組成s3的[0,i + j - 1]區(qū)間即真，即dp[i] [j] = (s1[i] == s3[i + j] && dp[i - 1] [j])
   
   (2)s2[j] == s3[i + j]。這個(gè)時(shí)候只要s1的[0, i]區(qū)間和s2的[0, j - 1]區(qū)間可以組成s3的[0,i + j - 1]區(qū)間即真，即dp[i] [j] = (s2[j] == s3[i + j] && dp[i] [j - 1])
   
   以上情況只要一個(gè)為真dp[i] [j]就為真。

3. 初始化
   為了避免越界以及方便初始化，我們引入空串的概念，多開一行一列。
   ①其中s1和s2都為空串可以組成空串s3，即dp[0][0] = true。
   
   ②當(dāng)s1為空串，s2不為空串(第一列除去[0, 0])的時(shí)候可以由s2單獨(dú)組成s3，前提是相等。即dp[0] [j] = true([1, j]區(qū)間s2與s3相等)。
   
   ③當(dāng)s2為空串，s1不為空串(第一行除去[0, 0])的時(shí)候可以由s1單獨(dú)組成s3，前提是相等。即dp[i] [0] = true([1, i]區(qū)間s1與s3相等)。

4. 填表順序
   填表不明白參考第一題，填表順序?yàn)?font color="red">行從上到下，每一行從左到右。

5. 返回值
   依據(jù)狀態(tài)表示，返回值為dp[m] [n]（m，n分別為s1、s2長度）。

• 代碼實(shí)現(xiàn)

class Solution
{
public:
    bool isInterleave(string s1, string s2, string s3) 
    {
        int m = s1.size(), n = s2.size();
        if(m + n != s3.size()) return false;  //兩者相加比s3長度小，一定沒辦法組成的
        s1 = " " + s1, s2 = " " + s2, s3 = " " + s3;  //處理下標(biāo)映射
        //dp[i][j]：s1的[1,i]區(qū)間和s2的[1,j]區(qū)間能否交錯(cuò)組成s3的[1,i+j]區(qū)間
        vector<vector<bool>> dp(m + 1, vector<bool>(n + 1));
        dp[0][0] = true;
        for(int j = 1; j <= n; j++) // 初始化第??，即s1為空，s2單獨(dú)組成s3
        {
            if(s2[j] == s3[j]) dp[0][j] = true;
            else break;
        }
        for(int i = 1; i <= m; i++) // 初始化第?列,即s2為空，s1單獨(dú)組成s3
        {
            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];
    }
};

6.兩個(gè)字符串的最小ASCII刪除和（中等）

鏈接：兩個(gè)字符串的最小ASCII刪除和

• 題目描述
  

• 做題步驟

1. 狀態(tài)表示
   有前面的做題經(jīng)驗(yàn)，我們定義一個(gè)二維表，定義狀態(tài)表示為dp[i] [j]：s1的[0, i]區(qū)間和s2的[0, j]區(qū)間要達(dá)到相同的最小刪除消耗。

2. 狀態(tài)轉(zhuǎn)移方程
   對(duì)s1的[0，i]區(qū)間和s2的[0，j]區(qū)間如何相同，我們分情況討論：
   (1)s1[i] == s2[j]時(shí)，只需要讓s1的[1, i - 1]和s2[1, j - 1]相同，即dp[i] [j] = dp[i - 1] [j - 1]。
   
   (2)s1[i] != s2[j]時(shí)，有兩種選擇：
   ①讓s1的[1, i - 1]和s2的[1, j]相同，把多余的s1[i]刪除，即dp[i] [j] = dp[i - 1] [j] + s1[i]。
   ②s1的[1, i]和s2的[1, j -1]相同，把多余的s2[j]刪除，即dp[i] [j] = dp[i] [j - 1] + s2[j]。
   ?、佗谇闆r的最小值即可，即(2)情況dp[i][j] = min(dp[i] [j - 1] + s2[j], dp[i - 1] [j] + s1[i])。
   
   這里提一下(1)情況的消耗是一定小于等于(2)的消耗，比如我一個(gè)短串和一個(gè)長串達(dá)到相等的消耗了x?，F(xiàn)在我在短串后面加一些字符，想達(dá)到相等的話消耗一定會(huì)大于等于x。

3. 初始化
   為了避免越界以及方便初始化，我們引入空串的概念，多開一行一列。
   ①當(dāng)s1和s2都為空串，消耗為0，即dp[0] [0] = 0。
   
   ②當(dāng)s1為空串，s2不為空串(第一列除去[0, 0])的時(shí)候s2必須全部刪除一直到為空串。即dp[0] [j] = dp[0] [j - 1] + s2[j] (j = 1; j <= n; j++)。
   
   ③當(dāng)s2為空串，s1不為空串(第一行除去[0, 0])的時(shí)候s1必須全部刪除一直到為空串。即dp[i] [0] = dp[i - 1] [0] + s1[i] (i = 1; i <= m; i++)。
   

4. 填表順序
   填表不明白參考第一題，填表順序?yàn)?font color="red">行從上到下，每一行從左到右。

5. 返回值
   依據(jù)狀態(tài)表示，返回值為dp[m] [n]（m，n分別為s1、s2長度）。

• 代碼實(shí)現(xiàn)

class Solution {
public:
    int minimumDeleteSum(string s1, string s2) {
        int m = s1.size(), n = s2.size();
        s1 = " " + s1, s2 = " " + s2;   //處理下標(biāo)映射
        //dp[i][j]:s1的[1,i]區(qū)間和s2的[1,j]區(qū)間要達(dá)到相同的最小刪除消耗
        vector<vector<int>> dp(m + 1, vector<int>(n + 1));
        //s1為空串,s2要?jiǎng)h除為空串的最小消耗
        for(int j = 1; j <= n; j++)
            dp[0][j] = dp[0][j - 1] + s2[j];
        //s2為空串，s1要?jiǎng)h除到空串的最小消耗
        for(int i = 1; i <= m; i++)
            dp[i][0] = dp[i - 1][0] + s1[i];

        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];
                else
                    dp[i][j] = min(dp[i][j - 1] + s2[j], dp[i - 1][j] + s1[i]);
            }
        return dp[m][n];
    }
};

7.最長重復(fù)子數(shù)組（中等）

鏈接：最長重復(fù)子數(shù)組

• 題目描述
  

• 做題步驟

1. 狀態(tài)表示
   這個(gè)題不難，但是注意它是子數(shù)組而不是子序列，我們用前面的方式定義狀態(tài)表示是會(huì)出錯(cuò)的，比如我定義狀態(tài)表示為dp[i] [j]：n1的[0, i]區(qū)間與n2的[0, j]區(qū)間中的公共最長子數(shù)組長度。
   拿n1 = [3, 1, 1]和n2 = [1, 0, 1]舉例，n1的[3, 1]區(qū)間和n2的[1, 0]區(qū)間公共最長子數(shù)組長度為1，當(dāng)n1[2] == n2[2]的時(shí)候，公共最長子數(shù)組是沒辦法算的，你想dp[i - 1][j - 1] + 1是絕對(duì)不行的，因?yàn)閚1[2]和n2[2]不一定能接在這個(gè)最長子數(shù)組后面，子數(shù)組必須是連續(xù)的?。。?br>
   前面以區(qū)間為關(guān)注對(duì)象，沒辦法推導(dǎo)狀態(tài)轉(zhuǎn)移方程，那我們就以n1[i]和n2[j]為子數(shù)組結(jié)尾進(jìn)行分析。
   我們定義一個(gè)二維表，定義狀態(tài)表示為dp[i] [j]：同時(shí)以n1的i位置和n2的j位置結(jié)尾的公共最長子數(shù)組長度。

2. 狀態(tài)轉(zhuǎn)移方程
   對(duì)n1[i]和n2[j]，我們分情況討論：
   (1)n1[i] == n2[j]時(shí)，可以同時(shí)接在以n1[i - 1]和n2[j - 1]為結(jié)尾的公共最長子數(shù)組后面，長度加1，即dp[i] [j] = dp[i - 1] [j - 1] + 1。
   
   (2)n1[i] != n2[j]時(shí)，同時(shí)以n1[i]和n2[j]為結(jié)尾的公共最長子數(shù)組不存在，即dp[i] [j] = 0。

3. 初始化
   為了避免越界，我們多開一行一列，dp數(shù)組下標(biāo)從1開始，多出來的一行一列初始化為0即可。（注意處理與n1和n2數(shù)組的下標(biāo)映射，因?yàn)閚1和n2數(shù)組是從下標(biāo)0開始的）

4. 填表順序
   填表順序?yàn)?font color="red">行從上到下，每一行從左到右。

5. 返回值
   沒法直接確定最長子數(shù)組的結(jié)尾，所以一邊dp一邊更新最大值。文章來源地址http://www.zghlxwxcb.cn/news/detail-712920.html

• 代碼實(shí)現(xiàn)

class Solution {
public:
    int findLength(vector<int>& n1, vector<int>& n2) {
        int m = n1.size(), n = n2.size();
        //dp[i][j]表示以nums1的i位置和nums2的j位置結(jié)尾的公共最長子數(shù)組長度
        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(n1[i - 1] == n2[j - 1])  //注意下標(biāo)映射
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                ret = max(ret, dp[i][j]);
            }
        return ret;
    }
};

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