更多干貨就在我的個(gè)人博客 BlackBlog.tech 歡迎關(guān)注！
也可以關(guān)注我的csdn博客：黑哥的博客
謝謝大家！

前面幾周完成了DFS、BFS的章節(jié)，一共大約40題左右，今天開始練習(xí)動(dòng)態(tài)規(guī)劃。動(dòng)態(tài)規(guī)劃是一種將原問題拆分成子問題，對(duì)子問題進(jìn)行求解，最終解決原文題的思想。動(dòng)態(tài)規(guī)劃適用于子問題不是獨(dú)立的情況，也就是各子問題包含公共的子子問題。
DP的關(guān)鍵在于尋找狀態(tài)轉(zhuǎn)移方程，即如何從前一狀態(tài)轉(zhuǎn)移到后一狀態(tài)，也可以理解為子問題的遞推公式。

動(dòng)態(tài)規(guī)劃設(shè)計(jì)的兩種方法：
自頂向下（又稱記憶化搜索、備忘錄）：基本上對(duì)應(yīng)著遞歸函數(shù)實(shí)現(xiàn)，從大范圍開始計(jì)算，要注意不斷保存中間結(jié)果，避免重復(fù)計(jì)算
自底向上（遞推）：從小范圍遞推計(jì)算到大范圍

其實(shí)前幾節(jié)搜索的問題很多也可以用DP的方式去求解。

給個(gè)目錄：
LeetCode63 不同路徑 II
LeetCode64 最小路徑和
LeetCode120 三角形最小路徑和
LeetCode91 解碼方法
LeetCode139 單詞拆分
LeetCode338 比特位計(jì)數(shù)
LeetCode357 計(jì)算各個(gè)位數(shù)不同的數(shù)字個(gè)數(shù)
LeetCode375 猜數(shù)字大小 II
LeetCode516 最長(zhǎng)回文子序列
LeetCode647 回文子串

LeetCode63 不同路徑 II

題目

一個(gè)機(jī)器人位于一個(gè) m x n 網(wǎng)格的左上角 （起始點(diǎn)在下圖中標(biāo)記為“Start” ）。
機(jī)器人每次只能向下或者向右移動(dòng)一步。機(jī)器人試圖達(dá)到網(wǎng)格的右下角（在下圖中標(biāo)記為“Finish”）。
現(xiàn)在考慮網(wǎng)格中有障礙物。那么從左上角到右下角將會(huì)有多少條不同的路徑？
網(wǎng)格中的障礙物和空位置分別用 1 和 0 來(lái)表示。
說明：m 和 n 的值均不超過 100。

示例 1:

輸入:
[
  [0,0,0],
  [0,1,0],
  [0,0,0]
]
輸出: 2
解釋:
3x3 網(wǎng)格的正中間有一個(gè)障礙物。
從左上角到右下角一共有 2 條不同的路徑：
1. 向右 -> 向右 -> 向下 -> 向下
2. 向下 -> 向下 -> 向右 -> 向右

C++代碼

class Solution {
public:
    int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
        int m = obstacleGrid.size(); //地圖高度
        int n = obstacleGrid[0].size(); ////地圖寬度
        vector<vector<int>> dp(m+1,vector<int>(n+1,0)); //初始化一個(gè)dp數(shù)組
        bool row_flag = true; //用來(lái)判斷第一行是否有1
        bool col_flag = true; //用來(lái)判斷第一列是否有1
        for(int i=0;i<n;i++){ //將第一行第一個(gè)障礙之前的所有點(diǎn) 標(biāo)記為1 表示有一種路徑可以到達(dá) 第一個(gè)障礙之后的所有點(diǎn)標(biāo)記為0 表示有0種路徑可達(dá)
            if(obstacleGrid[0][i]==1) row_flag = false; 
            if(row_flag) dp[0][i]=1;
            else dp[0][i]=0;
        }
        for(int i=0;i<m;i++){ //將第一列第一個(gè)障礙之前的所有點(diǎn) 標(biāo)記為1 表示有一種路徑可以到達(dá) 第一個(gè)障礙之后的所有點(diǎn)標(biāo)記為0 表示有0種路徑可達(dá)
            if(obstacleGrid[i][0]==1) col_flag = false;
            if(col_flag) dp[i][0]=1;
            else dp[i][0]=0;
        }
        for(int i=1;i<m;i++){
            for(int j=1;j<n;j++){ //從[1][1]開始計(jì)算到達(dá)每一點(diǎn)的路徑數(shù)，如果該點(diǎn)不是障礙則計(jì)算，狀態(tài)轉(zhuǎn)移方程為dp[i][j] = max(dp[i][j],dp[i-1][j]+dp[i][j-1])
                if(obstacleGrid[i][j]!=1) dp[i][j] = max(dp[i][j],dp[i-1][j]+dp[i][j-1]);
            }
        }
        return dp[m-1][n-1]; //返回右下角的值
    }
};

LeetCode64 最小路徑和

題目

給定一個(gè)包含非負(fù)整數(shù)的 m x n 網(wǎng)格，請(qǐng)找出一條從左上角到右下角的路徑，使得路徑上的數(shù)字總和為最小。

說明：每次只能向下或者向右移動(dòng)一步。

示例:

輸入:
[
  [1,3,1],
  [1,5,1],
  [4,2,1]
]
輸出: 7
解釋: 因?yàn)槁窂?1→3→1→1→1 的總和最小。

C++

class Solution {
public:
    int minPathSum(vector<vector<int>>& grid) {
        //dp數(shù)組表示從左上角到當(dāng)前點(diǎn)的最小路徑和
        int m = grid.size(); //矩陣的高度
        int n = grid[0].size(); //矩陣的寬度
        vector<vector<int>> dp(m+1,vector<int>(n+1,0)); //初始化一個(gè)dp數(shù)組
        dp[0][0] = grid[0][0]; //第一個(gè)點(diǎn)的最小路徑就是自己
        for(int i=1;i<n;i++){
            dp[0][i]=dp[0][i-1] + grid[0][i]; //初始化第一行 dp[0][i]=之前的路徑和+當(dāng)前路徑
        }
        for(int i=1;i<m;i++){
            dp[i][0] = dp[i-1][0] + grid[i][0]; //初始化第一列 dp[i][0]=之前路徑和+當(dāng)前路徑
        }
        for(int i=1;i<m;i++){
            for(int j=1;j<n;j++){
                dp[i][j] = min(dp[i-1][j],dp[i][j-1])+grid[i][j]; //狀態(tài)轉(zhuǎn)移方程 每一點(diǎn)最小路徑等與左點(diǎn) 上點(diǎn)中的較小值+當(dāng)前點(diǎn)的值
            }
        }
        return dp[m-1][n-1]; //返回右下角點(diǎn)
    }
};

體會(huì)

簡(jiǎn)單的DP題。dp[i][j]表示從左上角到[i]j]的最小路徑和，首先初始化第一行與第一列、第一行、第一列每一個(gè)最小路徑都等于前一個(gè)點(diǎn)的最小路徑加上當(dāng)前路徑，從[1][1]點(diǎn)開始后，狀態(tài)轉(zhuǎn)移方程為dp[i][j] = min(dp[i-1][j],dp[i][j-1])+grid[i][j]，每一點(diǎn)最小路徑等與 左點(diǎn) 上點(diǎn) 中的較小值+當(dāng)前點(diǎn)的值。最后返回右下角的點(diǎn)。

LeetCode120 三角形最小路徑和

題目

給定一個(gè)三角形，找出自頂向下的最小路徑和。每一步只能移動(dòng)到下一行中相鄰的結(jié)點(diǎn)上。

例如，給定三角形：

[
     [2],
    [3,4],
   [6,5,7],
  [4,1,8,3]
]

自頂向下的最小路徑和為 11（即，2 + 3 + 5 + 1 = 11）。

說明：

如果你可以只使用 O(n) 的額外空間（n 為三角形的總行數(shù)）來(lái)解決這個(gè)問題，那么你的算法會(huì)很加分。

C++代碼

int minimumTotal(vector<vector<int>> triangle) {
    int width = triangle[triangle.size()-1].size(); //三角形的最大寬度
    int depth = triangle.size(); //三角形最大高度
    vector<vector<int>> dp(triangle.size(),vector<int>(triangle[triangle.size()-1].size(),0));  //初始化一個(gè)dp數(shù)組
    //dp[i][j]表示從底部開始向上計(jì)算 第i行j列的最小路徑和
    for(int i=0;i<width;i++){ 
        dp[depth-1][i] = triangle[depth-1][i]; //初始化最后一行的值 最后一行的最小路路徑就是三角形的路徑
    }
    for(int i=depth-2;i>=0;i--){ //從倒數(shù)第二行向上開始計(jì)算
        for(int j=0;j<triangle[i].size();j++){//遍歷一行中的所有數(shù)據(jù)
            dp[i][j] = triangle[i][j] + min(dp[i+1][j],dp[i+1][j+1]);//狀態(tài)轉(zhuǎn)移方程 選出底下一行中較小的數(shù)字 將其與當(dāng)前三角形內(nèi)的值相加
        }
    }
    return dp[0][0]; //最終的結(jié)果
}

體會(huì)

一道基礎(chǔ)的DP題，從底向上進(jìn)行計(jì)算，dp[i][j]表示第i行j列的最小路徑和。從倒數(shù)第二行向上開始循環(huán)，狀態(tài)轉(zhuǎn)移方程為dp[i][j] = triangle[i][j] + min(dp[i+1][j],dp[i+1][j+1]);即選出底下一行中較小的數(shù)字，將其與當(dāng)前三角形內(nèi)的值相加。最終dp[0][0]為最終的結(jié)果。

LeetCode91 解碼方法

題目

一條包含字母 A-Z 的消息通過以下方式進(jìn)行了編碼：

'A' -> 1
'B' -> 2
...
'Z' -> 26

給定一個(gè)只包含數(shù)字的非空字符串，請(qǐng)計(jì)算解碼方法的總數(shù)。

示例 1:

輸入: "12"
輸出: 2
解釋: 它可以解碼為 "AB"（1 2）或者 "L"（12）。

示例 2:

輸入: "226"
輸出: 3
解釋: 它可以解碼為 "BZ" (2 26), "VF" (22 6), 或者 "BBF" (2 2 6) 。

C++代碼

class Solution {
public:
    int numDecodings(string s) {
        vector<int> dp(s.size()+1,0);
        dp[0]=1;
        //dp[i]表示前i位的解碼方式為dp[i]種
        for(int i=1;i<dp.size();i++){
            if(s[i-1]=='0') dp[i-1] = 0; //0 不能單獨(dú)解碼，dp[i-1]賦值為0
            if(s[i-2]=='1' || (s[i-2]=='2'&&s[i-1]<'7')) dp[i] = dp[i-1]+dp[i-2]; //如果十位為1或者十位為2 個(gè)位<7 ，證明這個(gè)數(shù)字可以按照兩位數(shù)進(jìn)行分解
            else dp[i] = dp[i-1]; // 如果不滿足分解情況，直接dp[i] = dp[i-1]
        }
        return dp[s.size()]; //返回dp[size]為最終的結(jié)果
    }
};

體會(huì)

斐波納切問題，建立一個(gè)dp數(shù)組，dp[i]表示前i為的解碼方式為dp[i]種。初值賦值為1，表示至少都有一種解碼方式，即逐個(gè)分割。之后對(duì)后面的數(shù)字進(jìn)行循環(huán)，如果遇到0，0不能單獨(dú)解碼，將dp[i-1]設(shè)置為0；如果遇到1開頭，或者2開頭且后一位小于7的數(shù)字，證明其可以看成一個(gè)兩位數(shù)，則多一種解碼方式，dp[i] = dp[i-1]+1; 最終輸出dp[s.size()]表示最終的結(jié)果。

LeetCode139 單詞拆分

題目

給定一個(gè)非空字符串 s 和一個(gè)包含非空單詞列表的字典 wordDict，判定 s 是否可以被空格拆分為一個(gè)或多個(gè)在字典中出現(xiàn)的單詞。

說明：

拆分時(shí)可以重復(fù)使用字典中的單詞。
你可以假設(shè)字典中沒有重復(fù)的單詞。
示例 1：

輸入: s = "leetcode", wordDict = ["leet", "code"]
輸出: true
解釋: 返回 true 因?yàn)?"leetcode" 可以被拆分成 "leet code"。

示例 2：

輸入: s = "applepenapple", wordDict = ["apple", "pen"]
輸出: true
解釋: 返回 true 因?yàn)?"applepenapple" 可以被拆分成 "apple pen apple"。
     注意你可以重復(fù)使用字典中的單詞。

示例 3：

輸入: s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"]
輸出: false

C++代碼

class Solution {
public:
    bool wordBreak(string s, vector<string>& wordDict) {
        if(s.size()<0 || wordDict.empty()) return false; //如果字符串長(zhǎng)度小于0，或者字典為空，則返回空值。
        unordered_set<string> dict; //將wordDict轉(zhuǎn)換成一個(gè)unordered_set,方便快速查詢
        for(auto key:wordDict) dict.insert(key); //將wordDict轉(zhuǎn)化為dict
        vector<bool> dp(s.size()+1,false); //創(chuàng)建一個(gè)dp數(shù)組 dp[i]表示前i個(gè)字符是否可以被拆分
        dp[0] = true; //初始值為true
        for(int i=1;i<=s.size();i++){ //前i個(gè)數(shù)字 字符串的終點(diǎn)
            for(int j=0;j<=i;j++){ //字符串的起點(diǎn)
                string new_str = s.substr(j,i-j); //i-j表示字符串的長(zhǎng)度 j表示字符串的起點(diǎn)
                if(dp[j] && dict.count(new_str)) { //dp[j]表示前j個(gè)字符是否可以被劃分（相當(dāng)于起點(diǎn)前的字符串被劃分） new_str是新的字符串 如果前面的字符串可以被劃分且new_str可以被劃分，則字符串前i個(gè)字符可以被劃分。
                    dp[i] = true;
                    break;
                }
            }
        }
        return dp[s.size()];
    }

};

體會(huì)

動(dòng)態(tài)規(guī)劃問題，判斷一個(gè)字符串是否可以劃分，只需要將其不斷拆分為小的字符串，判斷其是否可以劃分即可。dp[i]表示前i個(gè)字符是否可以劃分。i從1到size進(jìn)行循環(huán)，j從0到i進(jìn)行循環(huán)，i可以看成是子串的終點(diǎn)，j可以看成是子串的起點(diǎn)，如果dp[j]為true，表示前j個(gè)字符是可以劃分的，如果當(dāng)前的new_str可以劃分，那么證明前i個(gè)字符是可以劃分的，依次類推，循環(huán)整個(gè)字符串。

LeetCode338 比特位計(jì)數(shù)

題目

給定一個(gè)非負(fù)整數(shù) num。對(duì)于 0 ≤ i ≤ num 范圍中的每個(gè)數(shù)字 i ，計(jì)算其二進(jìn)制數(shù)中的 1 的數(shù)目并將它們作為數(shù)組返回。

示例 1:

輸入: 2
輸出: [0,1,1]

示例 2:

輸入: 5
輸出: [0,1,1,2,1,2]

進(jìn)階:

給出時(shí)間復(fù)雜度為O(n*sizeof(integer))的解答非常容易。但你可以在線性時(shí)間O(n)內(nèi)用一趟掃描做到嗎？
要求算法的空間復(fù)雜度為O(n)。
你能進(jìn)一步完善解法嗎？要求在C++或任何其他語(yǔ)言中不使用任何內(nèi)置函數(shù)（如 C++ 中的 __builtin_popcount）來(lái)執(zhí)行此操作。

C++代碼

class Solution {
public:
    vector<int> countBits(int num) {
        vector<int> dp(num+1,0);
        for(int i=1;i<=num;i++)
            dp[i] = dp[i>>1]+(i&1);//1001 可以看成是 100中1的個(gè)數(shù) + 最后一位是否為1 
        return dp;
    }
};

體會(huì)

這個(gè)題的關(guān)鍵就在于狀態(tài)轉(zhuǎn)移方程。1001中1的個(gè)數(shù)可以看作是100中1的個(gè)數(shù)加上最后一位是否為1，所以狀態(tài)狀態(tài)轉(zhuǎn)移方程為dp[i] = dp[i>>1]+(i&1)，若推導(dǎo)過程中用十進(jìn)制去思考，很難觀察到該狀態(tài)轉(zhuǎn)移方程。

LeetCode357 計(jì)算各個(gè)位數(shù)不同的數(shù)字個(gè)數(shù)

題目

給定一個(gè)非負(fù)整數(shù) n，計(jì)算各位數(shù)字都不同的數(shù)字 x 的個(gè)數(shù)，其中 0 ≤ x < 10n 。

示例:

輸入: 2
輸出: 91 
解釋: 答案應(yīng)為除去 11,22,33,44,55,66,77,88,99 外，在 [0,100) 區(qū)間內(nèi)的所有數(shù)字。

C++代碼

int countNumbersWithUniqueDigits(int n) {
    if(n==0) return 0; //0 1 2 這三種情況直接輸出
    if(n==1) return 10;
    if(n==2) return 91;
    if(n>2){
        int sum = 91;//兩位數(shù)中的各個(gè)位不同的數(shù)字有91個(gè)
        for(int j=3;j<=n;j++){
            int bit = 9; //第二位有9種情況
            int small_sum = 9; //第一位有9種情況
            for(int i=0;i<j-1;i++){
                small_sum = small_sum*bit; //各個(gè)位的情況相乘
                bit--; //從第二位開始往后每位可選擇的數(shù)字少一個(gè)
            }
            sum =  sum+small_sum;//統(tǒng)計(jì)所有數(shù)據(jù)
        }
        return sum;
    }
}

體會(huì)

組合排列問題。當(dāng)n=2時(shí)：十位有9種選擇，個(gè)位有9種選擇；當(dāng)n=3時(shí)，百位有9種選擇，十位有9種選擇，個(gè)位有8種選擇；當(dāng)n=4時(shí)，千位有9種選擇，百位有9種選擇，十位有8種選擇，個(gè)位有7種選擇。
所以：
n=2 9x9
n=3 9x9x8
n=4 9x9x8x7
以此類推，n在10以上后，必定有重復(fù)。

LeetCode375 猜數(shù)字大小 II

題目

我們正在玩一個(gè)猜數(shù)游戲，游戲規(guī)則如下：

我從 1 到 n 之間選擇一個(gè)數(shù)字，你來(lái)猜我選了哪個(gè)數(shù)字。

每次你猜錯(cuò)了，我都會(huì)告訴你，我選的數(shù)字比你的大了或者小了。

然而，當(dāng)你猜了數(shù)字 x 并且猜錯(cuò)了的時(shí)候，你需要支付金額為 x 的現(xiàn)金。直到你猜到我選的數(shù)字，你才算贏得了這個(gè)游戲。

示例:

n = 10, 我選擇了8.

第一輪: 你猜我選擇的數(shù)字是5，我會(huì)告訴你，我的數(shù)字更大一些，然后你需要支付5塊。
第二輪: 你猜是7，我告訴你，我的數(shù)字更大一些，你支付7塊。
第三輪: 你猜是9，我告訴你，我的數(shù)字更小一些，你支付9塊。

游戲結(jié)束。8 就是我選的數(shù)字。

你最終要支付 5 + 7 + 9 = 21 塊錢。

給定 n ≥ 1，計(jì)算你至少需要擁有多少現(xiàn)金才能確保你能贏得這個(gè)游戲。

C++代碼

class Solution {
public:
    int getMoneyAmount(int n) {
        vector<vector<int>> dp(n+1,vector<int>(n+1,0));
        //極小極大問題
        if(n<=2) return n-1;
        for(int i=2;i<=n;i++){ //i表示終點(diǎn)
            for(int j=i-1;j>0;j--){ //j表示起點(diǎn)
                int global = 999; //求最后的極小值 先初始化一個(gè)極大值
                int local = 0; //需要找到每一個(gè)子序列的極大值
                for(int k=j+1;k<i;k++){
                    local = k + max(dp[k+1][i],dp[j][k-1]); //狀態(tài)轉(zhuǎn)移方程
                    global = min(local,global); //最后取i j之間的最小值
                }
                dp[j][i] = j+1==i?j:global;
            }
        }
        return dp[1][n];//整個(gè)序列
    }
};

體會(huì)

這個(gè)題目的技巧性還是比較高的，狀態(tài)轉(zhuǎn)移方法比較難以尋找。
那么我們需要建立一個(gè)二維的dp數(shù)組，其中dp[i][j]表示從數(shù)字i到j(luò)之間猜中任意一個(gè)數(shù)字最少需要花費(fèi)的錢數(shù)，那么我們需要遍歷每一段區(qū)間[j, i]，維護(hù)一個(gè)全局最小值global_min變量，然后遍歷該區(qū)間中的每一個(gè)數(shù)字，計(jì)算局部最大值local_max = k + max(dp[j][k - 1], dp[k + 1][i])，這個(gè)正好是將該區(qū)間在每一個(gè)位置都分為兩段，然后取當(dāng)前位置的花費(fèi)加上左右兩段中較大的花費(fèi)之和為局部最大值，為啥要取兩者之間的較大值呢，因?yàn)槲覀円猚over所有的情況，就得取最壞的情況。然后更新全局最小值，最后在更新dp[j][i]的時(shí)候看j和i是否是相鄰的，相鄰的話賦為i，否則賦為global_min。這里為啥又要取較小值呢，因?yàn)閐p數(shù)組是求的[j, i]范圍中的最低cost，比如只有兩個(gè)數(shù)字1和2，那么肯定是猜1的cost低。

如果只有一個(gè)數(shù)字，那么我們不用猜，cost為0。
如果有兩個(gè)數(shù)字，比如1和2，我們猜1，即使不對(duì)，我們cost也比猜2要低。
如果有三個(gè)數(shù)字1，2，3，那么我們就先猜2，根據(jù)對(duì)方的反饋，就可以確定正確的數(shù)字，所以我們的cost最低為2。
如果有四個(gè)數(shù)字1，2，3，4，那么情況就有點(diǎn)復(fù)雜了，那么我們的策略是用k來(lái)遍歷所有的數(shù)字，然后再根據(jù)k分成的左右兩個(gè)區(qū)間，取其中的較大cost加上k。
當(dāng)k為1時(shí)，左區(qū)間為空，所以cost為0，而右區(qū)間2，3，4，根據(jù)之前的分析應(yīng)該取3，所以整個(gè)cost就是1+3=4。
當(dāng)k為2時(shí)，左區(qū)間為1，cost為0，右區(qū)間為3，4，cost為3，整個(gè)cost就是2+3=5。
當(dāng)k為3時(shí)，左區(qū)間為1，2，cost為1，右區(qū)間為4，cost為0，整個(gè)cost就是3+1=4。
當(dāng)k為4時(shí)，左區(qū)間1，2，3，cost為2，右區(qū)間為空，cost為0，整個(gè)cost就是4+2=6。
引自：https://blog.csdn.net/xuxuxuqian1/article/details/81636415

LeetCode516 最長(zhǎng)回文子序列

題目

給定一個(gè)字符串s，找到其中最長(zhǎng)的回文子序列。可以假設(shè)s的最大長(zhǎng)度為1000。

示例 1:

輸入:

"bbbab"
輸出:

4
一個(gè)可能的最長(zhǎng)回文子序列為 "bbbb"。

示例 2:

輸入:

"cbbd"
輸出:

2
一個(gè)可能的最長(zhǎng)回文子序列為 "bb"。

C++代碼

class Solution {
public:
    int longestPalindromeSubseq(string s) {
        string t = s;
        reverse(t.begin(),t.end()); //新建一個(gè)字符串 取反向 尋找公共子序列 就是最長(zhǎng)回文串
        return lcs(t,s);
    }
    int lcs(string src,string dst){
        int n = src.size();
        vector<vector<int>> dp(n+1,vector<int>(n+1,0)); //新建一個(gè)dp數(shù)組
        //dp數(shù)組初始化 第一行 第一列初始化為0
        for(int i=0;i<=n;i++) {
            dp[0][i] = 0;
            dp[i][0] = 0;
        } 
        
        for(int i=1;i<=n;i++){ //從第二個(gè)元素開始遍歷
            for(int j=1;j<=n;j++){
                if(src[i-1]==dst[j-1]) dp[i][j] = dp[i-1][j-1]+1; //狀態(tài)轉(zhuǎn)移方程
                else {
                    dp[i][j] = max(dp[i-1][j],dp[i][j-1]); 
                }
            }
        }
        return dp[n][n];
    }
};

體會(huì)

判斷最長(zhǎng)回文子串，只需要將一個(gè)字符串反轉(zhuǎn)后與原字符串求LCS，就是最長(zhǎng)回文子串。
LCS的狀態(tài)轉(zhuǎn)移方程比較簡(jiǎn)單。
0 if i=0 or j=0
c[i,j] = c[i-1,j-1]+1 if i,j>0 and xi = yj
max(c[i,j-1],c[i-1,j]) if i,j>0 and xi != yj
記住就好

LeetCode647 回文子串

題目

給定一個(gè)字符串，你的任務(wù)是計(jì)算這個(gè)字符串中有多少個(gè)回文子串。

具有不同開始位置或結(jié)束位置的子串，即使是由相同的字符組成，也會(huì)被計(jì)為是不同的子串。

示例 1:

輸入: "abc"
輸出: 3
解釋: 三個(gè)回文子串: "a", "b", "c".

示例 2:

輸入: "aaa"
輸出: 6
說明: 6個(gè)回文子串: "a", "a", "a", "aa", "aa", "aaa".

注意:

輸入的字符串長(zhǎng)度不會(huì)超過1000。

C++代碼

class Solution {
public:
    int help(string str,int left,int right){
        int count = 0;
        while(str[left]==str[right] && left>=0 && right<=str.size()-1){ //如果str[left]==str[right] 且沒有越界的情況下 向左右伸展 并記數(shù)
            count++; //記數(shù)
            left--; //向左伸展
            right++; //向右伸展
        }
        return count;
    }

    int countSubstrings(string s) {
        int sum = 0; //用來(lái)記數(shù)
        for(int i=0;i<s.size();i++){
            sum+= help(s,i,i); //長(zhǎng)度為奇數(shù)的回文數(shù)
            sum+= help(s,i,i+1); //長(zhǎng)度為偶數(shù)的回文數(shù)
        }
        return sum;
    }
};

體會(huì)

簡(jiǎn)單題，回文數(shù)有兩種情況，一種是長(zhǎng)度為奇數(shù)的回文數(shù)，一種是長(zhǎng)度為偶數(shù)的回文數(shù)，找到中間值，向兩邊伸展同時(shí)進(jìn)行判斷就可以。