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]
```