← 返回算法可视化主页

✂️ 分割回文串 划分型 DP · 最少分割次数

给定字符串 s,将其分割成若干子串,使每个子串都是回文串。求最少分割次数。

已算 0 答案 ?
就绪

📐 划分型 DP

将序列分成若干段,每段满足某种性质(回文)。dp[i] 表示前缀 s[0..i] 的最优解。

🔄 转移方程

dp[i] = min(dp[j-1] + 1),其中 s[j..i] 是回文串。若 s[0..i] 本身是回文,则 dp[i] = 0。

🧮 回文预处理

用 isPal[j][i] 表快速判断任意子串是否为回文,避免重复计算。

💡 说明
「下一步」 看划分型 DP 如何计算最少分割次数。
每步展示:检查回文 → 尝试分割 → 更新 dp。 键盘 ← → 控制,空格自动播放。

🔤 字符串

回文段 分割点 当前位置

📊 回文表 isPal[j][i] s[j..i] 是回文?

📊 dp[i]

🧮 当前计算

(等待开始)

🧩 分割方案

(等待开始)

📄 C++ 代码

行 1