664. Strange Printer
## 思路
印aaabbaaa的次數 = 印aba的次數 = 印ab的次數
先把連續重複的合起來 aaabbaaa -> aba
dp[left][right] = 範圍內最少print的次數
如果s[left] 跟 s[right] 字元一樣, 就回傳 dp[left][right-1]
不然就是在範圍內找k (s[left] == s[k]) 切割成兩個substring
## Complexity
Time: O(N^3)
Space: O(N^2)
## Code
Recursion
```python
class Solution:
def strangePrinter(self, s: str) -> int:
s = [ch for i, ch in enumerate(s) if i == len(s) -1 or ch != s[i+1]]
n = len(s)
@cache
def dp(left, right):
if left > right:
return 0
if left == right:
return 1
if s[left] == s[right]:
return dp(left, right-1)
res = float('inf')
for k in range(left, right):
if s[left] == s[k]:
res = min(res, dp(left, k) + dp(k+1, right))
return res
return dp(0, n-1)
```
Iteration
```python
class Solution:
def strangePrinter(self, s: str) -> int:
s = [ch for i, ch in enumerate(s) if i == len(s) -1 or ch != s[i+1]]
n = len(s)
dp = [[float('inf')] * n for _ in range(n)]
for i in range(n):
dp[i][i] = 1
for left in range(n-1, -1, -1):
for right in range(left+1, n):
if s[left] == s[right]:
dp[left][right] = dp[left][right-1]
else:
for k in range(left, right):
if s[left] == s[k]:
dp[left][right] = min(dp[left][right],
dp[left][k] + dp[k+1][right])
return dp[0][-1]
```