c++ - O(N ^ 2)时间内的回文分割问题

Question

问题描述:

Given a string s, partition s such that every substring of the partition is a palindrome. Return the minimum cuts needed for a palindrome partitioning of s.

Problem link

虽然我能够编写O(N ^ 3) solution，但是在O(N ^ 2)优化中面临问题

这是优化的 solution explanation

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

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

Answer 1

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