int minCut(char* s) {
int n = strlen(s);
bool g[n][n];
memset(g, 1, sizeof(g));
for (int i = n - 1; i >= 0; --i) {
for (int j = i + 1; j < n; ++j) {
g[i][j] = (s[i] == s[j]) && g[i + 1][j - 1];
}
}
int f[n];
for (int i = 0; i < n; ++i) {
f[i] = INT_MAX;
}
for (int i = 0; i < n; ++i) {
if (g[0][i]) {
f[i] = 0;
} else {
for (int j = 0; j < i; ++j) {
if (g[j + 1][i]) {
f[i] = fmin(f[i], f[j] + 1);
}
}
}
}
return f[n - 1];
}
相关文章
- 06-09【杂谈】AIGC之Stable Diffusion:AI绘画的魔法
- 06-09C语言 | Leetcode C语言题解之第132题分割回文串II-题解:
- 06-09【C++面向对象编程】(二)this指针和静态成员
- 06-09大数据之Schedule调度错误(一)
- 06-09开源模型应用落地-LangChain高阶-LCEL-表达式语言(三)
- 06-09AI推介-多模态视觉语言模型VLMs论文速览(arXiv方向):2024.05.25-2024.05.31
- 06-09C++学习/复习14--list的模拟实现(节点类/迭代器封装成类/list类/测试)
- 06-09appium自动化一之使用adb命令查找包名appPackage和appActivity
- 06-09代码随想录——修建二叉搜素树(Leetcode669)
- 06-09基于R语言APSIM模型进阶应用与参数优化、批量模拟-APSIM模型的农田管理措施的准备