664. Strange Printer

class Solution {
        public int strangePrinter(String s) {

        if (s == null || s.length() == 0) {
            return 0;
        }

        int n = s.length();
        int[][] state = new int[n][n];

        for (int i = 0; i < n; i++) {
            state[i][i] = 1;
        }

        for (int i = n - 1; i >= 0; i--) {
            for (int dist = 1; dist + i < n; dist++) {
                int j = dist + i;
                if (dist == 1) {
                    state[i][j] = (s.charAt(i) == s.charAt(j)) ? 1 : 2;
                    continue;
                }
                state[i][j] = Integer.MAX_VALUE;
                for (int k = i; k + 1 <= j; k++) {
                    int tmp = state[i][k] + state[k + 1][j];
                    state[i][j] = Math.min(state[i][j], tmp);
                }
                if (s.charAt(i) == s.charAt(j)) {
                    state[i][j]--;
                }
            }
        }

        return state[0][n - 1];
    }
}




class Solution {
    public int strangePrinter(String s) {
        Map<String, Integer> memo = new HashMap<>();

        return min_turns_to_print(0, s.length() - 1, s, memo);        
    }

    private int min_turns_to_print(int start, int end, String s, Map<String, Integer> memo) {
        if (start > end) {
            return 0;
        }
        
        String key = start + "-" + end;
        if (memo.containsKey(key)) {
            return memo.get(key);
        }
        
        int res = min_turns_to_print(start, end - 1, s, memo) + 1;

        for (int middle = start; middle < end; middle++) {
            if (s.charAt(middle) == s.charAt(end)) {
                res = Math.min(res, min_turns_to_print(start, middle, s, memo) + min_turns_to_print(middle + 1, end - 1, s, memo));
            }
        }
        
        memo.put(key, res);
        return res;
    }    
}