Below is my python dp solution for palindrome partition II.

Recursion Pseudo Code:

- Assign i=0,j= N-1
- minCut(S,0,N-1) = 0 (if Palindrome)
- else min(1 + minCut(s,1,N-1) ,1 + minCut(s,0,N-2))

The code seems to work fine for all the inputs except "bb" , which returns 1 for OJ instead of 0. But the solution works correctly and returns 0 in my system. Not sure what is wrong with the evaluation. Any help is appreciated. Thanks.

```
class Solution:
# @param s, a string
# @return a list of lists of string
part_dict = {}
def minCut(self, s):
return self.dp_compute_partition(s,0,len(s)-1)
def dp_compute_partition(self, s,i,j):
if (i , j) in self.part_dict:
return self.part_dict[(i , j)]
if i > j:
self.part_dict[(i , j)] = 0
elif s[i] == s[j]:
self.part_dict[(i,j)] = self.dp_compute_partition(s,i + 1,j-1)
else:
self.part_dict[(i,j)] = min(1 + self.dp_compute_partition(s,i+1,j), 1 + self.dp_compute_partition(s,i , j-1))
return self.part_dict[(i, j)]
```