Palindrome Partitioning — Min Cuts

for (int len = 1; len <= n; len++)
  for (int i = 0; i + len <= n; i++) {
    int j = i + len - 1;
    if (s[i] == s[j] && (len < 3 || isPalin[i+1][j-1]))
      isPalin[i][j] = true;
  }

for (int i = 0; i < n; i++) {
  if (isPalin[0][i]) { dp[i] = 0; continue; }
  dp[i] = i;
  for (int j = 1; j <= i; j++)
    if (isPalin[j][i])
      dp[i] = min(dp[i], dp[j-1] + 1);
}
return dp[n-1];