So I'm stuck in this DP problem.
The idea is easy, and it seems like a straight recursive+memoization approach.HOWEVER, that requires a 3D/4D array state and that's impossible since N<=1e5.(Every other state gave wrong answers)
This is the bruteforce O(3^N) function: - a is the lionishness, b is the snakiness and c is the goatism. - Lion, Snake and Goat are the three strings.
int solve(int i,int N,int a,int b,int c){
if(i == N) return min(a,b,c);
// either we take the ith letter from the lion's DNA
int p1 = solve(i+1,N,a+1,b+(Lion[i]==Snake[i]),c+(Lion[i]==Goat[i]));
// or from the snake's DNA
int p2 = solve(i+1,N,a+(Snake[i]==Lion[i]),b+1,c+(Snake[i]==Goat[i]));
// or from the goat's DNA
int p3 = solve(i+1,N,a+(Goat[i]==Lion[i]),b+(Goat[i]==Snake[i]),c+1);
return max(p1,p2,p3);
}
solve(0,N,0,0,0);
So I thought of making my approach iterative(since I read that it's always possible to do that and vice-versa) in order to(perhaps) be able to apply the memory optimization technique and solve it.
Here comes the issue, I was not able to make it iterative, nor to think of any alternatives.
On a side note, I do think that having only 4 letters can help, but can't seem to undersand how..
Any hints?
Thanks !