This problem is simiiar to #546 Remove Boxes which uses `f[l][r][k]`

to store the maximum points of range `[l, r]`

with `k`

boxes equal to `r`

. But for this problem, we can use 2D-array DP instead of 3D-array DP because the store of `k`

is useless.

`f[i][j]`

represents the minumum turns to print the sequence from `i`

to `j`

. The transition function should be:

```
f[i][j] = min(f[i][k] + f[k+1][j-1]) for each k where i<k<j and s[k]=s[j]
```

Do not forget the common transition:

```
f[i][j] = f[i][j-1] + 1
```

And the border condition:

```
f[i][j] = 0 where i>j
```

My C++ code is shown as below(with memorization):

```
#include <string>
#include <cmath>
class Solution
{
private:
int f[100][100];
private:
int dfs(const std::string& s, int l, int r)
{
if (l > r) return 0;
if (f[l][r]) return f[l][r];
f[l][r] = dfs(s, l, r - 1) + 1;
for (int i = l; i < r; ++i)
{
if (s[i] == s[r])
{
f[l][r] = std::min(f[l][r], dfs(s, l, i) + dfs(s, i + 1, r - 1));
}
}
return f[l][r];
}
public:
int strangePrinter(std::string s)
{
memset(f, 0, sizeof(f));
int len = (int)s.size();
return dfs(s, 0, len - 1);
}
};
```