664. Strange Printer (區間型 dp

Can see the screenshot explanation as well.

class Solution {
    public int strangePrinter(String s) {
        Integer[][] memo = new Integer[s.length()][s.length()];
        return dfs(s, 0, s.length()-1, memo);
    }
    private int dfs(String s, int i, int j, Integer[][] memo) {
        if (i == j) {
            return 1;
        }
        if (memo[i][j] != null) {
            return memo[i][j];
        }
        int minTurns = Integer.MAX_VALUE;
        for (int k = i; k < j; k++) {
            minTurns = Math.min(
                minTurns, 
                dfs(s, i, k, memo) + dfs(s, k+1, j,  memo)
            );
        }
        memo[i][j] = (s.charAt(i) == s.charAt(j) ? minTurns - 1 : minTurns);

        return memo[i][j];
    }
}

/**
This will seperate to all substring -> O(n^2)

Time Complexity Analysis
Subproblem Count:

The function helper(s, i, j, memo) is called for every possible substring s[i...j].
Since i can range from 0 to n-1 and j can range from i to n-1, 
the total number of unique subproblems is approximately the number of pairs (i, j) where i ≤ j.
There are
​n^2
such pairs, so the total number of subproblems is 
O(n^2).
Cost per Subproblem:

For each subproblem, the function attempts to split the string at every possible point k 
between i and j-1.
This involves checking up to j−i possible splits.
In the worst case, 
j−i can be as large as n−1.
Therefore, the time spent on each subproblem is 
O(n) 
Total Time Complexity:

Since there are 
O(n^2) subproblems, and each subproblem can take up to O(n) time to solve, 
the total time complexity is O(n^3)




thought

we want to find a break point to seperate to "2" part sub problem
keep do the dfs to sepeate to 2 part, until i == j (one char) so there is 1 turn 
ex: dfs(a) = 1 this is the base case

like
"aaabbb" -> to 
a aabbb 
or 
aa abbb 
or 
aaa bbb 
or
aaab bb
or 
aaabb b

see which one has the min turns

so we can record memo[i][j] which means from i to j the min turns in this substring

but notice, because when same char, we can print a seq, so like aaa -> only needs one turns, not 3 turns
so in every dfs(), we have to check if char[i] == char[j] -> then turns - 1

so dfs(aaa) = dfs(a) + dfs(aa) or dfs(aa) + dfs(a)
so dfs(aa) = dfs(a) + dfs(a) = 2 but char[i] == char[j], so dfs(aa) = 1
then dfs(aaa) = dfs(a) + dfs(aa) = 1+1 = 2, char[i] == char[j], so dfs(aaa) = 1
like a dfs 推論出來的結果！ this part is really hard!


ex1:
i.j
abc

because if runs a for in k
min(
dfs(a) + dfs(bc) = 1 + 2
,
dfs(ab) + dfs(c) = 2 +1 
)

dfs(bc) -> dfs(b) + dfs(c)


dfs(a) dfs(b) = 1+1 = 2

ex2:
aba
2 + 1 -> but (s.charAt(i) == s.charAt(j)) -> so 3 -1 = 2

ex3:

aaabbb
= min(
dfs(a) + dfs(aabbb)
or
dfs(aa) + dfs(abbb)
or
dfs(aaa) + dfs(bbb) = 
min(
dfs(a) + dfs(aa) + dfs(b) + dfs(bb) -> (so dfs(aa = 1), because but i == j)
dfs(aaa) = 2 -> but i == j so 2 -1 again
vice versa, dfs(bbb) = 1. so best ans is dfs(aaa) + dfs(bbb) = 1 + 1 = 2
or
dfs(aa) + dfs(a) + dfs(bb) + dfs(b)
)
or 
dfs(aaab) + dfs(bb)
or
dfs(aaabb) + dfs(b)
)

dfs(aabbb) =
min...

so actually we can find in i to j, the best solution, so it's a interval dp

we can use memo[i][j] to record the min turns in i to j
 */

refer to:

https://leetcode.com/problems/strange-printer/discuss/152758/Clear-Logical-Thinking-with-Code

refer to:

https://leetcode-cn.com/problems/strange-printer/solution/qu-jian-dpzhuang-tai-fang-cheng-de-tui-d-gjnk/

https://leetcode-cn.com/problems/strange-printer/solution/kan-bu-dong-zhe-dao-ti-mu-de-ke-yi-xian-t067e/

DFS + memo

T: O(n* (n/2)+(n/2) * (...) => ?

class Solution {
    public int strangePrinter(String s) {
        int n = s.length();
        Integer[][] memo = new Integer[n][n];
        return helper(s, 0, n - 1, memo);
    }
    private int helper(String s, int i, int j, Integer[][] memo) {
        if (i == j) {
            return 1;
        }
        if (memo[i][j] != null) {
            return memo[i][j];
        }
        int minTurns = Integer.MAX_VALUE;
        
        for (int k = i; k < j; k++) {
            minTurns = Math.min(
                minTurns,
                helper(s, i, k, memo) + helper(s, k+1, j, memo)
            );
        }
        memo[i][j] = (s.charAt(i) == s.charAt(j)) ? minTurns - 1 : minTurns;
        return memo[i][j];
    }
}

so

(s.charAt(i) == s.charAt(j)) ? minTurns - 1

dp

T: O(n^3)

S: O(n^2)

    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) {
        int n = s.length();
        
        int[][] dp = new int[n][n];
        for (int i = 0;i < n ;i++) {
            Arrays.fill(dp[i], Integer.MAX_VALUE/2);
        }
        for (int i = 0;i < n ;i++) {
            dp[i][i] = 1;
        }
        
        for (int len = 2; len <= n; len++) {
            for (int i = 0; i + len - 1 < n; i++) {
                int j = i + len - 1;
                dp[i][j] = 1 + dp[i+1][j];
                for (int k = i + 1; k < j ; k++) {
                    
                    if (s.charAt(k) == s.charAt(i)) {
                        dp[i][j] = Math.min(dp[i][j], dp[i][k-1] + dp[k+1][j]);
                    }
                }
                if (s.charAt(i) == s.charAt(j)) {
                    dp[i][j] = Math.min(dp[i][j], dp[i][j-1]);
                }
            }
        }
        return dp[0][n-1];
    }
}

/*
Given a string s, return the minimum number of turns the printer needed to print it.

can print new characters starting from and ending at any place and will cover the original existing characters.

可以再任意位置 replace





*/