public int minCut(String s) {
			if (s == null || s.length() == 0 || s.length() == 1) {
				return 0;
			}
			int[][] palindrome = new int[s.length()][s.length()];
			int[] cut_num = new int[s.length() + 1];

			for (int i = s.length() - 1; i >= 0; i--) {
				cut_num[i] = s.length() - i;
				for (int j = i; j < s.length(); j++) {
					if (s.charAt(i) == s.charAt(j)) {
						if (j - i < 2 || palindrome[i + 1][j - 1] == 1) {
							palindrome[i][j] = 1;
							cut_num[i] = Math.min(cut_num[i], cut_num[j + 1] + 1);
						}
					}
				}
			}
			return cut_num[0] - 1;
		}