@annieqt Came up with something nearly identical, here's my solution with some verbose comments:

/**
* In the case of the longestPalindromicSubsequence, we have analyzed substrings of a certain length
* in a sliding manner (ex: window of size 2, slide it from left to right. Then bump to size 3 and repeat).
*
* This technique is different. We stretch a prefix (S[i,j]) incrementally but explore all the substrings
* inside it in the process. So when j = 3, we explore substrings S[0,3], S[1,3], S[2,3] and S[3,3]. Like this,
* we traverse through all N^2 substrings and cleverly record whether they are palindromes.
* Everytime we isolate a non-trivial palindrome (i.e. length > 1) we then calculate the min cuts by using
* the results from the prefix of the prefix.
*
*/
public int minCut(String s) {
if (s.length() <= 1) return 0;
int n = s.length();
int[] dp = new int[n];
boolean[][] pal = new boolean[n][n];
for(int j = 0; j < n; j++) {
int min = j;
for(int i = 0; i <= j; i++) {
char c1 = s.charAt(i), c2 = s.charAt(j);
/*
* Four cases that you could encounter
* 1. i and j point to the same index, so characters are the same and the substring is a pal
* 2. i and j point to adjacent indices, so the substring is a pal
* 3. i and j are wide apart, but the substring between them has been observed to be a pal
* 4. i and j point to different characters. Nothing worthwhile to pursue here
*/
if (c1 == c2 && (j - i < 2 || pal[i+1][j-1])) {
pal[i][j] = true;
if (i == 0) {
// the whole prefix from the beginning is a palindrome, no cuts needed
min = 0;
} else {
// pay the cost of 1 cut, and what the prefix of the prefix requires
min = Math.min(min, dp[i-1] + 1);
}
}
}
dp[j] = min;
}
return dp[n-1];
}