LeetCode 132 Palindrome Partitioning II - Walkthrough

Find minimum cuts to partition $s = \text{"aab"}$ into palindromes. First, precompute $isPalin[i][j]$ = true if $s[i..j]$ is a palindrome. $dp[i]$ = min cuts for $s[0..i]$.

If $s[0..i]$ is palindrome, $dp[i] = 0$. Else, try all cuts. $dp[0] = 0$ ("a"). $dp[1] = 0$ ("aa" is palindrome). $dp[2] = 1$ ("aab" needs cut: "aa" + "b"). Pre-computing the palindrome table avoids redundant checks during the DP. This is a common preprocessing pattern.