public static int minCut(String s) {
        // write your code here
        int n=s.length();
        boolean[][] t=new boolean[n][n];
        for (int i=0;i<n;++i) {
            t[i][i]=true;
            if (i+1<n)
                t[i][i+1]=s.charAt(i)==s.charAt(i+1);
        }
        for (int l=2;l<n;++l) {
            for (int i=0;i+l<n;++i) {
                t[i][i+l]|=t[i+1][i+l-1]&&s.charAt(i)==s.charAt(i+l);
            }
        }
        int[]dp=new int[n+1];
        for (int i=1;i<=n;++i) {
            if (t[0][i-1])
                dp[i]=0;
            else {
                dp[i]=Integer.MAX_VALUE;
                for (int j=1;i-j>0;++j) {
                    if (t[i-j][i-1])
                        dp[i]=Math.min(dp[i], dp[i-j]+1);
                }
            }
        }
        return dp[n];
    }