O（N ^ 2）时间中的回文分割问题

Question

问题描述：

给定一个字符串s，分区s，使得分区的每个子字符串都是回文。返回s的回文分区所需要的最小割点。

Problem link

虽然我能够编写O（N ^ 3）solution，但在O（N ^ 2）优化中遇到问题

这是优化的solution explanation

在第一行中，“ [cut [i]是cut [j-1]的最小值+ 1（j <= i），如果[j，i]是回文”]

为什么会这样？形式证明不是必需的，直觉也可以。

Answer 1

如果S[j..i]是回文，则该部分（从j到i）说明了ith有效切割（以及公式中的+ 1）。由于我们已经为此迭代确定了有效的ith剪切，所以我们要做的就是为字符串的前面部分找到最佳的整体最小剪切。在动态程序中，每次迭代通常会存储总体上的最佳累积值，这意味着我们不需要回头看j-1，而是可以尝试多个j。