典型的动态规划问题:
- 对于每个位置i,以递增的方式找长度为
1,3,5,7...
的回文子串,然后找长度为2,4,6,8
的回文子串; - 假设回文子串的起始位置为
idx_s
,结束位置为idx_e
,更新dp数组的公式为dp[idx_e] = min(dp[idx_s-1] + 1, dp[idx_e])
- 考虑到
idx_s=0
的情况,我们将dp[0]置为-1
代码如下:
// // Created by jt on 2020/8/23. // #include <vector> #include <string> using namespace std; class Solution { public: /** * * @param s string字符串 * @return int整型 */ int minCut(string s) { // write code here // dp[0] = 0, dp[1] = 0, dp[i] = min(dp[j] + 1, dp[j]) 其中0<=j<i int sz = s.size(); vector<int> dp(sz+1, INT_MAX); dp[0] = -1; for (int i = 0; i < sz; ++i) { // 回文长度为1, 3, 5, 7, 9... for (int len = 0; i - len >= 0 && i + len < sz && s[i-len] == s[i+len]; len++) { dp[i+len+1] = min(dp[i+len+1], dp[i-len] + 1); } // 回文长度为2, 4, 6, 8, 10... for (int len = 0; i - len >= 0 && i + len + 1 < sz && s[i-len] == s[i+len+1]; len++) { dp[i+len+2] = min(dp[i+len+2], dp[i-len] + 1); } } return dp[sz]; } };