Given a matrix of n*n. Each cell contain 0, 1, -1.
0 denotes there is no diamond but there is a path. 1 denotes there is diamond at that location with a path -1 denotes that the path is blocked.
Now you have start from 0,0 and reach to last cell & then return back to 0,0 collecting maximum no of diamonds. While going to last cell you can move only right and down. While returning back you can move only left and up.
This also came in one of my tests. Couldn't come up with anything good. One thing is clear that running naive algorithm twice will give incorrect results.
It is same as two paths moving simultaneously from start to end. So we can see the distance travelled is always same i.e there are on same diagonal at each moment. So a dp with states as (diagonal,pos1,pos2) can be done with O(1) transitions. Hence O(n*n*n).
Can you please tell me why standard approach won't work here? That is normal maxCost path.
You cannot just take a path with maximum diamonds twice, you need to consider if a certain diamond was taken or not when going back
Nice. Missed it. Thanks!
https://www.topcoder.com/community/competitive-programming/tutorials/dynamic-programming-from-novice-to-advanced/
Check the advanced section