更多干貨就在我的個(gè)人博客 BlackBlog.tech 歡迎關(guān)注霜医！
也可以關(guān)注我的csdn博客：黑哥的博客
謝謝大家齿拂！
前面幾周完成了DFS、BFS的章節(jié)支子，一共大約40題左右创肥，今天開始練習(xí)動(dòng)態(tài)規(guī)劃。動(dòng)態(tài)規(guī)劃是一種將原問題拆分成子問題值朋，對子問題進(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ì)的兩種方法：
自頂向下（又稱記憶化搜索、備忘錄）：基本上對應(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 最長回文子序列
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 來表示愁憔。
說明：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; //用來判斷第一行是否有1
bool col_flag = true; //用來判斷第一列是否有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)格脓恕，請找出一條從左上角到右下角的路徑，使得路徑上的數(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ì)
簡單的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ù)）來解決這個(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ù)字的非空字符串偎蘸，請計(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è)分割误澳。之后對后面的數(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; //如果字符串長度小于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表示字符串的長度 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果元。對于 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++或任何其他語言中不使用任何內(nèi)置函數(shù)（如 C++ 中的 __builtin_popcount）來執(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ù)字，你來猜我選了哪個(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，即使不對透硝，我們cost也比猜2要低狰闪。
如果有三個(gè)數(shù)字1，2濒生，3埋泵，那么我們就先猜2，根據(jù)對方的反饋罪治，就可以確定正確的數(shù)字秋泄，所以我們的cost最低為2。
如果有四個(gè)數(shù)字1规阀，2，3瘦麸，4谁撼，那么情況就有點(diǎn)復(fù)雜了，那么我們的策略是用k來遍歷所有的數(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 最長回文子序列
題目
給定一個(gè)字符串s，找到其中最長的回文子序列陆淀】加啵可以假設(shè)s的最大長度為1000。
示例 1:
輸入:
"bbbab"
輸出:
4
一個(gè)可能的最長回文子序列為 "bbbb"轧苫。
示例 2:
輸入:
"cbbd"
輸出:
2
一個(gè)可能的最長回文子序列為 "bb"楚堤。
C++代碼
class Solution {
public:
int longestPalindromeSubseq(string s) {
string t = s;
reverse(t.begin(),t.end()); //新建一個(gè)字符串 取反向 尋找公共子序列 就是最長回文串
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ì)
判斷最長回文子串，只需要將一個(gè)字符串反轉(zhuǎn)后與原字符串求LCS含懊，就是最長回文子串身冬。
LCS的狀態(tài)轉(zhuǎ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".
注意:
輸入的字符串長度不會(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; //用來記數(shù)
for(int i=0;i<s.size();i++){
sum+= help(s,i,i); //長度為奇數(shù)的回文數(shù)
sum+= help(s,i,i+1); //長度為偶數(shù)的回文數(shù)
}
return sum;
}
};
體會(huì)
簡單題剿配，回文數(shù)有兩種情況搅幅，一種是長度為奇數(shù)的回文數(shù)，一種是長度為偶數(shù)的回文數(shù)呼胚，找到中間值茄唐，向兩邊伸展同時(shí)進(jìn)行判斷就可以。
