【LeetCode】132.分割回文列II結題報告(C++)

原題住所:https://leetcode-cn.com/problems/palindrome-partitioning-ii/description/
タイトルの説明:
文字列sが与えられ、sはいくつかのサブストリングに分割され、各サブストリングがエコーストリングであるようにする.
要求に合致する最小分割回数を返します.
例:
入力:「aab」出力:1解釈:一度分割すればsを[「aa」,「b]]のような2つの回文子列に分割できる.
 
問題解決方案:
ダイナミックプランニングのテーマは論理的な要求が本当に高いので、このような問題型に直面して、高校数列の数学の問題とすればいいです.前に得られた結果から現在の位置の結果が押し出され、前の要素から後の要素の結果が押し出されます.後件要素の結果を導くには、エラーが発生しないように、すべての状況を考慮する必要があります.
次に,動的計画のモデル,すなわち配列を構築することも重要である.

class Solution {
public:
    int isPalin(string& str, int begin, int end) {
        while (begin < end)
            if (str[begin] != str[end])
               return 0;
            else {
                begin++;    end--;
            }
        return 1;
    }
    
    int minCut(string s) {
        if (s.size() <= 1) return 0;
        int dp[s.size()];
        for (int i = 0; i < s.size(); i++) {
            dp[i] = isPalin(s, 0, i) == 1? 0:i;
            for (int j = 1; j <= i; j++)
                if (isPalin(s, j, i))
                    dp[i] = min(dp[i], dp[j - 1] + 1);
        }
        return dp[s.size() - 1];
    }
};