动态规划算法拔萝卜c++代码

动态规划算法拔萝卜的 C++ 代码如下所示：

int minCut(string s) {
int size = s.length();
if (size == 0 || size == 1) return 0;

vector<vector<int>> dp(size, vector<int>(size, 0));
vector<int> min_cut(size + 1, size - 1);
min_cut = -1;

for (int i = 0; i < size; i++) {
for (int j = 0; j <= i; j++) {
if (s[i] == s[j] && (i - j <= 1 || dp[j + 1][i - 1])) {
dp[j][i] = 1;
min_cut[i + 1] = min(min_cut[i + 1], min_cut[j] + 1);
}
}
}

return min_cut[size];
}