我的往期文章：
leetCode 647.回文子串 動(dòng)態(tài)規(guī)劃 + 優(yōu)化空間 / 中心擴(kuò)展法 + 雙指針-CSDN博客https://blog.csdn.net/weixin_41987016/article/details/133883091?spm=1001.2014.3001.5501leetCode 131.分割回文串 + 回溯算法 + 圖解 + 筆記-CSDN博客https://blog.csdn.net/weixin_41987016/article/details/134700907?spm=1001.2014.3001.5501（一）利用動(dòng)態(tài)規(guī)劃來(lái)優(yōu)化判斷回文子串
- 利用動(dòng)態(tài)規(guī)劃高效地事先一次性計(jì)算出, 針對(duì)一個(gè)字符串
s, 它的任何子串是否是回文字串, 然后在我們的回溯函數(shù)中直接查詢即可, 省去了雙指針移動(dòng)判定這一步驟.（來(lái)自代碼隨想錄Carl老師的原話）原文鏈接：代碼隨想錄 (programmercarl.com)
>>思路和分析
回文子串：講究的是這個(gè)字符串里邊左右兩邊是對(duì)稱的，左右兩邊的元素是相同的。如果只判斷這個(gè)字符串的最左面和最右面這兩個(gè)元素相同的情況下，還知道中間的子串已經(jīng)是回文的，那么就可以直接判斷整個(gè)字符串它就是回文子串。
也就是說，如果在[i+1,j-1]范圍的子串是一個(gè)回文串，再向兩邊拓展遍歷的時(shí)候，那只需要判斷兩邊這兩個(gè)元素是否相同就可以了。若相同，dp[i][j]是回文串。
>>動(dòng)規(guī)五部曲
1.確定dp數(shù)組以及下標(biāo)的含義
- dp[i][j]:表示區(qū)間范圍[i,j]的子串是否為回文子串。如果是，則dp[i][j] = true,否則為false
- 或者說，dp[i][j] 表示截取從 i 到 j 的子串是否為回文子串
2.確定遞推式
if(j == i) dp[i][j]=true;
else if(j-i == 1) dp[i][j] = (s[i]==s[j]);
else dp[i][j] = (s[i] == s[j] && dp[i+1][j-1]);3.dp 數(shù)組初始化
- dp[i][j]初始化為false
4.確定遍歷順序
一定要從下到上，從左到右遍歷，這樣能保證dp[i+1][j-1]是經(jīng)過計(jì)算得來(lái)的
?5.舉例推導(dǎo)dp數(shù)組
void computePalindrome(const string& s) {
// dp[i][j] 代表s[i:j]（雙邊包括）是否是回文子串
dp.resize(s.size(),vector<bool>(s.size(),false));// 根據(jù)字符串s，刷新布爾矩陣的大小
for(int i=s.size()-1;i>=0;i--) {
// 需要倒序計(jì)算，保證在i行時(shí)，i+1行已經(jīng)計(jì)算好了
for(int j=i;j<s.size();j++) {
if(j == i) dp[i][j]=true;
else if(j-i == 1) dp[i][j] = (s[i]==s[j]);
else dp[i][j] = (s[i] == s[j] && dp[i+1][j-1]);
}
}
}"aebeaeccfcce"
1 0 0 0 1 0 0 0 0 0 0 0
0 1 0 1 0 0 0 0 0 0 0 0
0 0 1 0 0 0 0 0 0 0 0 0
0 0 0 1 0 1 0 0 0 0 0 0
0 0 0 0 1 0 0 0 0 0 0 0
0 0 0 0 0 1 0 0 0 0 0 1
0 0 0 0 0 0 1 1 0 0 1 0
0 0 0 0 0 0 0 1 0 1 0 0
0 0 0 0 0 0 0 0 1 0 0 0
0 0 0 0 0 0 0 0 0 1 1 0
0 0 0 0 0 0 0 0 0 0 1 0
0 0 0 0 0 0 0 0 0 0 0 1
"acgcabbfcc"
1 0 0 0 1 0 0 0 0 0
0 1 0 1 0 0 0 0 0 0
0 0 1 0 0 0 0 0 0 0
0 0 0 1 0 0 0 0 0 0
0 0 0 0 1 0 0 0 0 0
0 0 0 0 0 1 1 0 0 0
0 0 0 0 0 0 1 0 0 0
0 0 0 0 0 0 0 1 0 0
0 0 0 0 0 0 0 0 1 1
0 0 0 0 0 0 0 0 0 1 （二）分割回文串 + 動(dòng)態(tài)規(guī)劃 + 回溯算法 + 優(yōu)化
class Solution {
public:
vector<vector<string>> result;
vector<string> path; // 放已經(jīng)回文的子串
vector<vector<bool>> dp; // 放事先計(jì)算好的是否回文子串的結(jié)果
void backtracking(const string& s,int startIndex) {
// 如果起始位置已經(jīng)大于 s 的大小，說明已經(jīng)找到了一組分割方案了
if(startIndex >= s.size()) {
result.push_back(path);
return;
}
for(int i=startIndex;i<s.size();i++) {
if(dp[startIndex][i]) { // 是回文子串
// 獲取[startIndex,i] 在 s 中的子串
string subStr = s.substr(startIndex,i-startIndex+1);
path.push_back(subStr);
}else continue; // 不是回文，跳過
backtracking(s,i+1);// 尋找 i+1 為起始位置的子串
path.pop_back();// 回溯過程，彈出本次已經(jīng)添加的子串
}
}
void computePalindrome(const string& s) {
// dp[i][j] 代表s[i:j]（雙邊包括）是否是回文子串
dp.resize(s.size(),vector<bool>(s.size(),false));// 根據(jù)字符串s，刷新布爾矩陣的大小
for(int i=s.size()-1;i>=0;i--) {
// 需要倒序計(jì)算，保證在i行時(shí)，i+1行已經(jīng)計(jì)算好了
for(int j=i;j<s.size();j++) {
if(j == i) dp[i][j]=true;
else if(j-i == 1) dp[i][j] = (s[i]==s[j]);
else dp[i][j] = (s[i] == s[j] && dp[i+1][j-1]);
}
}
}
vector<vector<string>> partition(string s) {
computePalindrome(s);
backtracking(s, 0);
return result;
}
};參考和推薦文章：
代碼隨想錄 (programmercarl.com)https://www.programmercarl.com/0131.%E5%88%86%E5%89%B2%E5%9B%9E%E6%96%87%E4%B8%B2.html#%E6%80%9D%E8%B7%AF
摘選代碼隨想錄的總結(jié)：文章來(lái)源：http://www.zghlxwxcb.cn/news/detail-753521.html
- 總結(jié)難點(diǎn)：
- 如何切割？切割問題可以抽象為組合問題
- 如何模擬那些切割線？
- 切割問題中遞歸如何終止？
- 在遞歸循環(huán)中如何截取子串？
- 如何判斷回文？
遞歸用于縱向遍歷，for循環(huán)用于橫向遍歷當(dāng)切割線迭代至字符串末尾，說明找到一種方法。類似組合問題，為了不重復(fù)切割同一位置，利用?start_index?作為標(biāo)記，記錄下一輪。遞歸的起始位置（切割線）。切割過的地方不能重復(fù)切割，故遞歸函數(shù)傳入 i+1文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-753521.html
到了這里，關(guān)于leetCode 131.分割回文串 + 動(dòng)態(tài)規(guī)劃 + 回溯算法 + 優(yōu)化 + 圖解 + 筆記的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
