# C++ 29ms DP solution

• 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);
}
};
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.