662.md

664. Strange Printer

Solution 1 (time O(n^3), space O(n^2))

# Dynamic programming
class Solution(object):
    def strangePrinter(self, s):
        """
        :type s: str
        :rtype: int
        """
        n = len(s)
        dp = [[0 for _ in range(n + 1)] for _ in range(n + 1)]
        for cur_len in range(1, n + 1):
            for cur_left in range(n - cur_len + 1):
                cur_right = cur_left + cur_len - 1
                dp[cur_left][cur_right] = dp[cur_left + 1][cur_right] + 1
                for i in range(cur_left + 1, cur_right + 1):
                    if s[cur_left] == s[i]:
                        dp[cur_left][cur_right] = min(dp[cur_left][cur_right],
                                                      dp[cur_left][i - 1] + dp[i + 1][cur_right])
        return dp[0][n - 1]