**I think most of the solutions posted here using 2-dimensional dp are wrong, but accidentally pass all the test cases:**

Most of the solutions are using:

`dp[i][j]`

: minimum print for the interval `[i, j]`

or `[i, j)`

, and use that to do recursion. But I think this is incorrect: since it also depend on the printing of the previous time. For example, if the `[i,j]`

has been printed by `'a'`

for the last time, then it is no longer the same as the initial state, since we do not need to print `'a'`

within this interval again.

Here is my solution:

I use a 3D array `dp[i][j][k]`

do denote the minimum print need for the interval `[j, k)`

if this interval was printed by `char('a' + i -1)`

(`i = 0`

if this it has not being printed).

Then during the recursion, not only we need to consider about indices `t`

s.t. `s[t] == s[j]`

but also need to consider `t`

s.t. `s[t] == char('a' + i -1)`

.

Am I wrong? (*Maybe I am wrong.*)

Below is my solution:

```
typedef vector<int> vi;
class Solution {
int dp [27][105][105], pos[27][105];
string st;
int n;
int cnt(int ic,int i,int j){
if(i>j) return 0;
if(dp[ic][i][j] >= 0) return dp[ic][i][j];
if(ic == (int)(st[i]-'a' + 1)) return dp[ic][i][j] = cnt(ic,i+1,j);
if(ic == (int)(st[j]-'a' + 1)) return dp[ic][i][j] = cnt(ic,i,j-1);
int kc = (int)(st[i]-'a' + 1), k = min(pos[kc][i], pos[ic][i]);
dp[ic][i][j] = n;
while(true){
k = min(j+1, k);
dp[ic][i][j] = min(dp[ic][i][j], 1 + cnt(kc,i+1,k-1) + cnt(ic,k+1,j));
if(k >= j) break;
k = min(pos[kc][k], pos[ic][k]);
}
return dp[ic][i][j];
}
public:
int strangePrinter(string s) {
if(s.empty()) return 0;
st += s[0];
for(int i=1;i<s.size();++i) if(s[i]!=s[i-1]) st+=s[i];
n = st.size();
memset(dp,-1,sizeof(dp));
memset(pos,0,sizeof(pos));
map<char,int> mp;
for(int i=0;i<27;++i) pos[i][n-1] = n;
for(int j=n-2;j>=0;--j) for(int i=0;i<27;++i){
if(i == (int)(st[j+1]- 'a' + 1)) pos[i][j] = j+1;
else pos[i][j] = pos[i][j+1];
}
return cnt(0,0,n-1);
}
};
```