664.md

664 Strange Printer

Description

link

---

Solution

dp[i][j] : the minimum number of turns the printer needed in order to print s[i:j + 1]

Recursive : dp[i][j] = min(dp[i][j], dp[i + 1][k - 1] + dp[k][j]) for all i, k satisfies s[i] == s[k]

Init : res = 1 if i == j else dp[i + 1][j] + 1

---

Code

Complexity T : O(n^3) M : O(n^2)

class Solution:
    def strangePrinter(self, s):
        """
        :type s: str
        :rtype: int
        """
        n = len(s)
        
        dp = [[0] * n for _ in range(n)]
        for i in range(n - 1, -1, -1):
            for j in range(i, n):
                tmp = 1 if i == j else dp[i + 1][j] + 1
                for k in range(i + 1, j + 1):
                    if s[i] == s[k]:
                        tmp = min(tmp, dp[i + 1][k - 1] + dp[k][j])
                dp[i][j] = tmp
        return 0 if n == 0 else dp[0][-1]