Beats 100%, dp memoization with precalculated distance matrix O(n^2 * 2^n)
\n\n\n# Intuition\n\nWith the exception of positions near corners, the minimum # of moves between 2 points P1 and P2 depends only on the relative positions of t
![chrome-capture-2024-9-11.png](https://assets.leetcode.com/users/images/b0a973a3-aeba-4ffc-ba15-446c5cf350ac_1726080971.9759948.png)\n\n\n# Intuition\n\nWith the exception of positions near corners, the minimum # of moves between 2 points P1 and P2 depends only on the relative positions of the two points.  We can use a compile time matrix of all possible relative positions [-49;49] in each dimension to quickly get the distance between each pair of pawns, with the exception of those where both pawns in the pair are within 3 cells of the same corner, calculating those edge cases separately. \n\n# Approach\n\nDP memoization using a bitmap of remaining pawn position indices and the current position index, as per the problem hints, using the matrix discussed in the intuition section.\n\nThe same dp array is shared for Alice and Bob, as with one taking odd turns and the other even turns, they can never have the same number of remaining positions set in the bitmap and therefore never collide.\n\n# Complexity\n- Time complexity:\nO($2^n$ * $n^2$)\nO($2^n$ * $n$) elements used in the memoization array, with one AliceHelper or BobHelper call associated with each of these, which contains a worst case O($n$) loop.\n\n- Space complexity:\nO($2^n$ * $n$)\n\n# Code\n\nThe hardcoded compile-time distance grid makes it too big to allow posting here! But we can link the submission: https://leetcode.com/problems/maximum-number-of-moves-to-kill-all-pawns/submissions/1386906650\n
['C++']