AIO DP Problem

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 !

Read more…(139 words)

About the author:

Ilyes Ltifi

Loading…

Join the discussion. Add a reply…

Post

About the author

Ilyes Ltifi

Ready to join our community?

Sign up below to automatically get notified of new lists, get **reminders** to finish ones you subscribe to, and **bookmark** articles to read later.

Continue with Facebook

— OR —

Your Full Name

Email address

I have an account. Log in instead

By signing up, you agree to our Terms and our Privacy Policy.