This page explains Java solution to problem `Strange Printer`

using `Dynamic Programming`

algorithm.

There is a strange printer with the following two special requirements:

- 1. The printer can only print a sequence of the same character each time.
- 2. At each turn, the printer can print new characters starting from and ending at any places, and will cover the original existing characters.

Given a string consists of lower English letters only, your job is to count the minimum number of turns the printer needed in order to print it.

Input: "aaabbb"Output: 2Explanation: Print "aaa" first and then print "bbb".

Input: "aba"Output: 2Explanation: Print "aaa" first and then print "b" from the second place of the string, which will cover the existing character 'a'.

```
package com.vc.hard;
class StrangePrinter {
public int strangePrinter(String s) {
if(s == null || s.length() == 0) return 0;
int n = s.length();
int[][] dp = new int[n][n];
for(int len = 0; len < n; len++) {
for(int from = 0; from + len < n; from++) {
int to = from + len;
if(len == 0) dp[from][to] = 1;
else {
dp[from][to] = Integer.MAX_VALUE;
for(int middle = from; middle < to; middle++) {
dp[from][to] = Math.min(dp[from][to],
dp[from][middle] + dp[middle + 1][to]);
}
if(s.charAt(from) == s.charAt(to)) dp[from][to]--;
}
}
}
return dp[0][n - 1];
}
}
```

O(N

^{3})

O(N

^{2})