# Most posts are wrong. (Or Am I wrong？)

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

• Please provide a link to such a wrong solution and show an input where that solution returns a wrong result. (It's strange that you didn't do that right away.)

• This post is deleted!

• @brendon4565
for the update `dp[i][j] -> min(dp[i][k] + dp[k+1][j])` for all `k` where `i<=k<=j` && `a[i] == a[k]`:
When the interval `[i, k]` be overwritten once by `a[i]`, it is no longer the initial state (You do not need to print `a[i]` within this interval again, but for the initial state, you need.). Then the minimum prints need to cover this interval from this state is `dp[i][k]|_{a[i]}` which is not necessarily equal to `dp[i][k]` which is the minimum print of this interval from the very beginning when no character has been printed.
I will try to construct a case when I get time.

• @ManuelP
I will try to construct a case when I get time.
I am not 100% percent sure. I might be wrong.

• @pkuitachi
You are wrong.
Here is the proof

I upvoted this post anyways, though, because I feel it was constructive and exposed an assumption in people's O(n^3) algorithms that needed to be examined rigorously.

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