//O(n) space!! //O(n^2) time!!! public class Solution { public int minCut(String s) { if(s == null || s.length() <= 1) return 0; int len = s.length(); int[] dp = new int[len+1]; for(int i = 0; i <= len; i++){ dp[i] = i-1; // initial to current char numbers -1 as the most cut } for(int i = 0; i < len; i++){ for(int j = 0; i-j>=0 && i+j=0 && i+j