public static int cut(int i, String s, int[] cut, int[][] pal) {

		if (cut[i] != 0) {
			return cut[i];
		}
		if (pal(0, i, s, pal) == 2) {
			cut[i] = 0;
			return 0;
		}

		int min = i;
		for (int k = 1; k <= i; k++) {
			if (pal(k, i, s, pal) == 2) {
				int tmp = cut(k - 1, s, cut, pal) + 1;
				if (tmp < min) {
					min = tmp;
				}
			}
		}
		cut[i] = min;

		return min;
	}