這篇“C++如何拆分回文串”文章的知識點大部分人都不太理解，所以小編給大家總結(jié)了以下內(nèi)容，內(nèi)容詳細，步驟清晰，具有一定的借鑒價值，希望大家閱讀完這篇文章能有所收獲，下面我們一起來看看這篇“C++如何拆分回文串”文章吧。

10年積累的成都做網(wǎng)站、成都網(wǎng)站制作、成都外貿(mào)網(wǎng)站建設經(jīng)驗，可以快速應對客戶對網(wǎng)站的新想法和需求。提供各種問題對應的解決方案。讓選擇我們的客戶得到更好、更有力的網(wǎng)絡服務。我雖然不認識你，你也不認識我。但先網(wǎng)站策劃后付款的網(wǎng)站建設流程，更有邊壩免費網(wǎng)站建設讓你可以放心的選擇與我們合作。

解法一：

class Solution {
public:
    int minCut(string s) {
        if (s.empty()) return 0;
        int n = s.size();
        vector> p(n, vector(n));
        vector dp(n);
        for (int i = 0; i < n; ++i) {
            dp[i] = i;
            for (int j = 0; j <= i; ++j) {
                if (s[i] == s[j] && (i - j < 2 || p[j + 1][i - 1])) {
                    p[j][i] = true;
                    dp[i] = (j == 0) ? 0 : min(dp[i], dp[j - 1] + 1);
                }
            }
        }
        return dp[n - 1];
    }
};

我們也可以反向推，這里的dp數(shù)組的定義就剛好跟前面反過來了，dp[i] 表示區(qū)間 [i, n-1] 內(nèi)的最小分割數(shù)，所以最終只需要返回 dp[0] 就是區(qū)間 [0, n-1] 內(nèi)的最喜哦啊分割數(shù)了，極為所求。然后每次初始化 dp[i] 為 n-1-i 即可，j 的更新范圍是 [i, n)，此時我們就只需要用 1 + dp[j+1] 來更新 dp[i] 了，為了防止越界，需要對 j == n-1 的情況單獨處理一下，整個思想跟上面的解法一模一樣，請參見之前的講解。

解法二：

class Solution {
public:
    int minCut(string s) {
        if (s.empty()) return 0;
        int n = s.size();
        vector> p(n, vector(n));
        vector dp(n);
        for (int i = n - 1; i >= 0; --i) {
            dp[i] = n - i - 1;
            for (int j = i; j < n; ++j) {
                if (s[i] == s[j] && (j - i <= 1 || p[i + 1][j - 1])) {
                    p[i][j] = true;
                    dp[i] = (j == n - 1) ? 0 : min(dp[i], dp[j + 1] + 1);
                }
            }
        }
        return dp[0];
    }
};

下面這種解法是論壇上的高分解法，沒用使用判斷區(qū)間 [i, j] 內(nèi)是否為回文串的二維dp數(shù)組，節(jié)省了空間。但寫法上比之前的解法稍微有些凌亂，也算是個 trade-off 吧。這里還是用的一維dp數(shù)組，不過大小初始化為了 n+1，這樣其定義就稍稍發(fā)生了些變化，dp[i] 表示由s串中前 i 個字母組成的子串的最小分割數(shù)，這樣 dp[n] 極為最終所求。接下來就要找狀態(tài)轉(zhuǎn)移方程了。這道題的更新方式比較特別，跟之前的都不一樣，之前遍歷 i 的時候，都是更新的 dp[i]，這道題更新的卻是 dp[i+len+1] 和 dp[i+len+2]，其中 len 是以i為中心，總長度為 2*len + 1 的回文串，比如 bob，此時 i=1，len=1，或者是i為中心之一，總長度為 2*len + 2 的回文串，比如 noon，此時 i=1，len=1。中間兩個for循環(huán)就是分別更新以 i 為中心且長度為 2*len + 1 的奇數(shù)回文串，和以 i 為中心之一且長度為 2*len + 2 的偶數(shù)回文串的。i-len 正好是奇數(shù)或者偶數(shù)回文串的起始位置，由于我們定義的 dp[i] 是區(qū)間 [0, i-1] 的最小分割數(shù)，所以 dp[i-len] 就是區(qū)間 [0, i-len-1] 范圍內(nèi)的最小分割數(shù)，那么加上奇數(shù)回文串長度 2*len + 1，此時整個區(qū)間為 [0, i+len]，即需要更新 dp[i+len+1]。如果是加上偶數(shù)回文串的長度 2*len + 2，那么整個區(qū)間為 [0, i+len+1]，即需要更新 dp[i+len+2]。這就是分奇偶的狀態(tài)轉(zhuǎn)移方程，參見代碼如下：

解法三：

class Solution {
public:
    int minCut(string s) {
        if (s.empty()) return 0;
        int n = s.size();
        vector dp(n + 1, INT_MAX);
        dp[0] = -1;
        for (int i = 0; i < n; ++i) {
            for (int len = 0; i - len >= 0 && i + len < n && s[i - len] == s[i + len]; ++len) {
                dp[i + len + 1] = min(dp[i + len + 1], 1 + dp[i - len]);
            }
            for (int len = 0; i - len >= 0 && i + len + 1 < n && s[i - len] == s[i + len + 1]; ++len) {
                dp[i + len + 2] = min(dp[i + len + 2], 1 + dp[i - len]);
            }
        }
        return dp[n];
    }
};

以上就是關于“C++如何拆分回文串”這篇文章的內(nèi)容，相信大家都有了一定的了解，希望小編分享的內(nèi)容對大家有幫助，若想了解更多相關的知識內(nèi)容，請關注創(chuàng)新互聯(lián)行業(yè)資訊頻道。