LeetCode 132 Palindrome Partitioning II - Two DPs

First, precompute $isPalin[i][j]$ = true if $s[i..j]$ is a palindrome. This is itself an interval DP: $isPalin[i][j]$ = ($s[i]$ == $s[j]$) && $isPalin[i+1][j-1]$.

Then, define $cuts[i]$ = minimum cuts for $s[0..i]$. If $s[0..i]$ is a palindrome, $cuts[i]$ = 0. Otherwise, try all j where $s[j+1..i]$ is a palindrome: $cuts[i]$ = min($cuts[j]$ + $1$). This is 1D (one-dimensional) DP using the 2D (two-dimensional) precomputation. Total time: $O(n^2)$.

Time complexity: $O(n^2)$.

Space complexity: $O(n^2)$ for the dp arrays.