# Easiest Java DP Solution (97.36%)

• This can be solved by two points:

1. `cut[i]` is the minimum of `cut[j - 1] + 1 (j <= i)`, if `[j, i]` is palindrome.
2. If `[j, i]` is palindrome, `[j + 1, i - 1]` is palindrome, and `c[j] == c[i]`.

The 2nd point reminds us of using dp (caching).

``````a   b   a   |   c  c
j  i
j-1  |  [j, i] is palindrome
cut(j-1) +  1
``````

Hope it helps!

``````public int minCut(String s) {
char[] c = s.toCharArray();
int n = c.length;
int[] cut = new int[n];
boolean[][] pal = new boolean[n][n];

for(int i = 0; i < n; i++) {
int min = i;
for(int j = 0; j <= i; j++) {
if(c[j] == c[i] && (j + 1 > i - 1 || pal[j + 1][i - 1])) {
pal[j][i] = true;
min = j == 0 ? 0 : Math.min(min, cut[j - 1] + 1);
}
}
cut[i] = min;
}
return cut[n - 1];
}``````

• I got exactly same code as yours, except that here I use

``````(j + 1 >= i - 1)
``````

and this increases total time largely from 12ms to 32ms.

• Sounds like a typical branch prediction issue to me, but why would it happen here? I am at a loss. It's not like the condition changes randomly on each iteration.

• one guess is <= means smaller or equal, it's two comparisons while < is only one. Imagine how you are going to translate it into compiler.

• Not likely. a <= b is probably translated as `sub a, b; jle ...`, a < b is `sub a, b; jl ...`. While technically `jle` is `SF <> OF || ZF == 0` and `jl` is just `SF <> OF`, but it's one machine instruction either way and should be blazingly fast unless you hit branch prediction problems because that is what makes these instructions slow, not the actual comparison.

• I think your solution is very easy to understand. Just to make sure, the runtime is O(n^2) right? Thanks.

• @D_shaw Actually that's just a LeetCode server issue.

Sometimes it's 30+, sometimes it's 10+.

Well, this kind of small wave always happens. Not a big issue.

• It's a very neat solution, but it uses O(n^2) space, isn't it?

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.