题目：
给定一个字符串str，返回把str全部切成回文子串的最小分割数。
举例：
str=“ABA” ，不需要切割，返回0；
str=“ACDCDCDAD”，最少需要切两次，比如"A",“CDCDC”,“DAD”，所以返回2.
#include <bits/stdc++.h> using namespace std; int D[100]; bool check(string S, int s, int e) { while (s <= e) { if (S[s] != S[e]) return false; s++; e--; } return true; } int dp(string S) { for (int i = 1; i < S.size(); ++i) { D[i] = check(S, 0, i) ? 0 : i + 1; for (int t = i; t >= 1; --t) { if (check(S, t, i)) { D[i] = min(D[i], D[t - 1] + 1); } } } return D[S.size() - 1]; } int main() { while (true) { string S; cin >> S; cout << dp(S) << endl; for (int i = 0; i < S.size(); ++i) cout << D[i] << '\t'; system("pause"); } }