This question was asked was in an OA. I was not able to sovle it fully i.e my soln got partially accepted.
Question
Code
Constraints
I want to solve this problem via memorization as I am not so good at writing bottom-up approach directly.
I took 5 states-> X and Y coordinates of alice and bob and index of the corr(array of position of apples). How to optimize states?
Thanks in advance.
Firstly, observe that there are only $$$n+2$$$ locations/coordinates you care about: the $$$n$$$ apples and starting locations of Alice and Bob. So a naive dp state might look like $$$dp[Current\;apple][Alice\;location][Bob\;location]$$$. However this is $$$n^3$$$ and is likely too slow for given constraints.
When you are at apple $$$i$$$, are all $$$n^2$$$ location pairs possible for Alice and Bob?
The person who collected apple $$$i$$$ must be a location $$$i$$$. The other person can, in theory, be in any of the previous locations.
You dp state can now look like $$$dp[Current\;apple][One\;player's\;location]$$$. The other player's location is implicitly the position of the current apple. Transitions look like $$$dp[i][pos]\rightarrow dp[i+1][pos]$$$ with cost = $$$d(i^{th} apple, (i+1)^{th} apple)$$$, or $$$dp[i][pos]\rightarrow dp[i+1][i^{th}\;apple]$$$ with cost = $$$d(pos, (i+1)^{th}\;apple)$$$.
Really inspiring reduction in dimension.
Which college are you from??