Проблема разбиения палиндрома за время O (N ^ 2)

Question

Описание проблемы:

Учитывая строку s, раздел s такой, что каждая подстрока раздела является палиндромом. Верните минимальные сокращения, необходимые для разделения палиндромом s.

Ссылка на проблему

Хотя я смог кодировать O (N ^ 3) решение но сталкивается с проблемой в O (N ^ 2) оптимизации

Это оптимизированное объяснение решения

В самой первой строке "cut [i] is минимум среза [j - 1] + 1 (j <= i), если [j, i] - палиндром "</p>

Почему это так? Формальные доказательства не обязательны, интуиция тоже подойдет.

Answer 1

Если S[j..i] - палиндром, то в этом разделе (от j до i) учитывается действительное сокращение ith (и + 1 в формуле). Так как для этой итерации мы исправили допустимое значение ith, все, что нам нужно сделать, - это найти наилучший общий минимальный разрез для предыдущей части строки. В динамической c программе каждая итерация обычно хранит общее кумулятивное значение наилучшим образом, что означает, что нам не нужно оглядываться назад, чем j-1, но у нас есть несколько j s, чтобы попробовать.