private static int cost(int i, int j) {
//		System.out.println("i" + i);
//		System.out.println("j" + j);
        if (cache[i][j] >= 0) return cache[i][j];
        if (i + 1 == j) return (input[i] == 'x' ? 0 : 1); // 1 element.
        if (i == j) return 1; // no elements

        int minCost = Integer.MAX_VALUE;


        if (input[j - 1] == '*') { // keep last, costs us nothing
            for (int k = i; k <= j - 1; k++) {
                int currentCost = cost(i, k) + cost(k, j - 1);
                minCost = Math.min(minCost, currentCost);
            }
        } else { // replace
            for (int k = i; k <= j - 1; k++) {
                int currentCost = cost(i, k) + cost(k, j - 1) + 1;
                minCost = Math.min(minCost, currentCost);
            }
        }
        minCost = Math.min(minCost, cost(i, j - 1) + 1); // delete

        for (int k = i+1; k < j; k++) { // insert
            int currentCost = cost(i, k) + cost(k, j) + 1;
            minCost = Math.min(minCost, currentCost);
        }
        cache[i][j] = minCost;
        return minCost;
    }