##### ###### ##### ### # # ### # # ###### ## ## ## ## ## ## ## # # # # # ## ##### #### ##### # # # # # # # #### ## # ## ## ## ## # # # # # ## ## # ###### ## ### # ### # ######
##### ###### ##### ### # # ### # # ###### ## ## ## ## ## ## ## # # # # # ## ##### #### ##### # # # # # # # #### ## # ## ## ## ## # # # # # ## ## # ###### ## ### # ### # ######
Precompute + solve
First, precompute = true if is a palindrome. This is itself an interval DP: = ( == ) && . Then, define = minimum cuts for . If is a palindrome, = 0. Otherwise, try all j where is a palindrome: = min( + ). This is 1D (one-dimensional) DP using the 2D (two-dimensional) precomputation. Total time: .
Time complexity: .
Space complexity: for the dp arrays.
