Palindrome Partitioning II

Given a string s, partition s such that every substring of the partition is a palindrome.

Return the minimum cuts needed for a palindrome partitioning of s.

For example, given s = "aab",
Return 1 since the palindrome partitioning ["aa","b"] could be produced using 1 cut.

Solution:
First try: dfs: time limit exceeded.
Second try: dp without cache valid palindrome. time limit exceeded.
Third try: dp with cache valid palindrome.
Valid palindrome iteration formula: dp[i][j] = dp[i+1][j-1] && s[i]==s[j] ? true : false;

public class Solution {
    public int minCut(String s) {
        int len = s.length();
        int[] dp = new int[len];
        boolean[][] p = new boolean[len][len];
        
        for(int i = 0; i < len; i++) dp[i] = i;
        for(int i = 0; i < len; i++)
            for(int j = 0; j < len; j++)
                p[i][j] = false;
        
        for(int j = 0; j < len; j++){
            for(int i = 0; i <= j; i++){
                if((j-i<=1 || p[i+1][j-1] == true) && s.charAt(i) == s.charAt(j))
                    p[i][j] = true;
                if(p[i][j] == true && i >= 1){
                    dp[j] = Math.min(dp[j], dp[i-1]+1);
                }
            }
            if(p[0][j] == true) dp[j] = 0;
        }
        return dp[len-1];
    }
}