跟著九章侯老師學(xué)習(xí)了動(dòng)態(tài)規(guī)劃專題之后根據(jù)學(xué)習(xí)所總結(jié)：
1 題目描述
給你一個(gè)字符串 s，請(qǐng)你將 s 分割成一些子串，使每個(gè)子串都是回文。
返回符合要求的 最少分割次數(shù) 。
2 示例
2.1 示例 1：
輸入：s = “aab”
輸出：1
解釋：只需一次分割就可將 s 分割成 [“aa”,“b”] 這樣兩個(gè)回文子串。
2.2 示例 2：
輸入：s = “a”
輸出：0
2.3 示例 3：
輸入：s = “ab”
輸出：1
2.4 提示：
1 <= s.length <= 2000
s 僅由小寫英文字母組成
來源：力扣（LeetCode）
鏈接：https://leetcode.cn/problems/palindrome-partitioning-ii
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有。商業(yè)轉(zhuǎn)載請(qǐng)聯(lián)系官方授權(quán)，非商業(yè)轉(zhuǎn)載請(qǐng)注明出處。
3 解題思路和方法
3.1 解題思路
3.1.1 確定狀態(tài)
- 最后一步：關(guān)注最優(yōu)策略中最后一段回文串，設(shè)為S[j…N-1];
- 需要知道S前j個(gè)字符[0…j-1]最少可以劃分成幾個(gè)回文串
- 子問題：
- 狀態(tài)：設(shè)S前i個(gè)字符S[0…i-1]最少可以劃分成f[i]個(gè)回文串
3.1.2 轉(zhuǎn)移方程
- 設(shè)S前i個(gè)字符S[0…i-1]最少可以劃分成f[i]個(gè)回文串
3.1.3 初始條件和邊界情況
- 設(shè)S前i個(gè)字符S[0…i-1]最少可以劃分成f[i]個(gè)回文串
- 初始化條件：空串可以被分成0個(gè)回文串 f[0] = 0
3.1.4 計(jì)算順序
計(jì)算f[0],f[1],f[2],…,f[N]
3.1.5 回文串的判斷方法
根據(jù)奇和偶數(shù)回文串的特點(diǎn)采用下面的方式去處理
文章來源：http://www.zghlxwxcb.cn/news/detail-496393.html
3.2 算法代碼實(shí)現(xiàn)
- 首先判斷回文串
for (int i = n - 1; i >= 0; --i) {
for (int j = i + 1; j < n; ++j) {
g[i][j] = (s[i] == s[j]) && g[i + 1][j - 1];
}
}
- 根據(jù)遍歷的字符串是否為回文串計(jì)算最少劃分次數(shù)
for (int j = 0; j < i; ++j) {
if (g[j + 1][i]) {
f[i] = fmin(f[i], f[j] + 1);
}
}
最終算法代碼實(shí)現(xiàn)如下所示：文章來源地址http://www.zghlxwxcb.cn/news/detail-496393.html
int minCut(char* s) {
int n = strlen(s);
bool g[n][n];
memset(g, 1, sizeof(g));
for (int i = n - 1; i >= 0; --i) {
for (int j = i + 1; j < n; ++j) {
g[i][j] = (s[i] == s[j]) && g[i + 1][j - 1];
}
}
int f[n];
for (int i = 0; i < n; ++i) {
f[i] = INT_MAX;
}
for (int i = 0; i < n; ++i) {
if (g[0][i]) {
f[i] = 0;
} else {
for (int j = 0; j < i; ++j) {
if (g[j + 1][i]) {
f[i] = fmin(f[i], f[j] + 1);
}
}
}
}
return f[n - 1];
}
到了這里，關(guān)于動(dòng)態(tài)規(guī)劃-分割回文串 II的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
