C++ | Well explained intuition and solution | O(n * 2^n) time and space complexity
Intuition\nThis is a game theory problems. You would\'ve previously seen problems where 2 players play with different strategies to try to win a game. \n\n### M
# Intuition\nThis is a game theory problems. You would\'ve previously seen problems where 2 players play with different strategies to try to win a game. \n\n### Minimax Algorithm:\nThe minimax algorithm is a standard way to solve two-player problems optimally where both players play perfectly. It works as follows:\n\n**Maximizing Player:** One player tries to maximize their payoff or score (here Alice).\n**Minimizing Player:** The other player tries to minimize the payoff of the maximizing player (here Bob).\n\n### How to solve these kind of problems - \nIn each step, the algorithm explores all possible moves:\n\nThe maximizing player chooses the move that gives the highest possible score.\n\nThe minimizing player chooses the move that gives the lowest possible score for the maximizing player.\nSteps:\n\n1. **Generate all possible moves for the current player.**\n2. For each move, simulate the resulting state of the game.\n3. **Use recursion to evaluate the result of every possible future move for both players.**\n4. Define when the game ends (in our case when all the pawns are captured).\n4. Backtrack through the moves to determine the optimal sequence for both players.\n\n# Approach\nBased on the algorithm described above, we will write a recursive solution when Alice and Bob play alternatively as per their respective stragegies.\n\nNow, if you notice there\'s some scope of pre computation to solve this with better time complexity. Note: even if we don\'t pre compute, our solution would still be correct, just it would not pass the time limit imposed.\n\nLet\'s say our knight is at position `(si, sj)` where our last pawn was captured and now we want to capture next pawn at `(di, dj)`, we can pre compute how many moves (minimum) are required for knight to go from `(si, sj)` to `(di, dj)`.\n\nNow, how do we track which pawns are captured and which are yet to be. Since there are only 15 pawns at max, we can use a bitmask - (1 << 15) which will be 32768. Note, we could also have used a visited array, but the though of bitmask brings to our next optimization which is memoization (i.e. dynamic programming). This will be more clear one you see recursive function.\n\n# Complexity\n- Time complexity: $$O(n * 2^n)$$\nThis is defined by the number of recursive calls.\n\n- Space complexity: $$O(n * 2^n)$$ where n is the number of pawns.\nThe largest space allocated is of dp array which - 15*2 *(1<<15) = 983040 which is also the depth of recursion.\n\n# Code\n```cpp []\nclass Solution {\npublic:\n\n    // knight moves (x, y)\n    int kmoves[8][2] = {\n        {2, 1},\n        {2, -1},\n        {-2, 1},\n        {-2, -1},\n        {1, 2},\n        {1, -2},\n        {-1, 2},\n        {-1, -2}\n    };\n    \n    // movesToOtherPawns returns the shortest number of moves starting \n    // from (px, py) to all other positions (i, j) on the chessboard\n    vector<vector<int>> movesToOtherPawns(int px, int py) {\n        vector<vector<int>> moves(50, vector<int>(50, INT_MAX));\n\n        queue<pair<int, int>> q;\n        // start from (px, py)\n        moves[px][py] = 0;\n        q.push({px, py});\n        int m = 1;\n\n        while(!q.empty()) {\n            int sz = q.size();\n            \n            while(sz--) {\n                auto f = q.front();\n                q.pop();\n\n                for(auto &next :kmoves) {\n                    int x = f.first + next[0], y = f.second + next[1];\n                    \n                    // checking for out of bounds and if we\'ve already visited (x, y)\n                    if (x < 0 || x >= 50 || y < 0 || y >= 50 || moves[x][y] <= m)\n                        continue;\n                                \n                    moves[x][y] = m; \n                    q.push({x, y});\n                }\n            }\n\n            m++;\n        }\n\n        return moves;\n    }\n\n    int go(int i, int isAliceTurn, int bitmask, vector<vector<int>>& positions, vector<vector<vector<int>>> &pawnMoves, int dp[15][2][1 << 15]) {\n        // if all pawns are captured, game is over\n        if (i == pawnMoves.size()) {\n            return 0;\n        }\n\n        // check if answer is memoized\n        int &ans = dp[i][isAliceTurn][bitmask];\n        if (ans != -1) {\n            return ans;\n        }\n\n        if (isAliceTurn)\n            ans = INT_MIN;\n        else\n            ans = INT_MAX;\n\n        for(int j=0; j<positions.size(); j++) { \n            if (bitmask & (1 << j))\n                continue;   // this pawn is already visited\n\n            int x = positions[j][0], y = positions[j][1];\n            int moves = pawnMoves[i][x][y];\n                \n            int recAns = go(j, !isAliceTurn, bitmask | (1 << j), positions, pawnMoves, dp);\n\n            // Alice\'s strategy is to maximize the moves\n            if (isAliceTurn)\n                ans = max(ans, moves + recAns);\n            else\n            // Bob\'s strategy is to minimize the moves\n                ans = min(ans, moves + recAns);\n        }\n\n        // edge case where for loop does not run even once.\n        if (ans == INT_MAX || ans == INT_MIN)\n            ans = 0;\n\n        return ans;\n    }\n    \n    int maxMoves(int kx, int ky, vector<vector<int>>& positions) {\n        // precompute the move kinght has to move to reach each pawn.\n        vector<vector<int>> kinghtMoves = movesToOtherPawns(kx, ky);\n        \n        // precompute the moves required from each pawn to all other pawns\n        vector<vector<vector<int>>> pawnMoves;\n        for(auto &p: positions) {\n            pawnMoves.push_back(movesToOtherPawns(p[0], p[1]));\n        }\n\n        int maxAns = 0;\n\n        // dp array to memoize \n        int dp[15][2][1 << 15];\n        memset(dp, -1, sizeof(dp));\n\n        for(int i=0; i<positions.size(); i++) {\n            // alice makes her first move by capturing one of the pawns.\n            int px = positions[i][0], py = positions[i][1];\n            int moves = kinghtMoves[px][py];\n\n            int ans = go(i, 0, 1 << i, positions, pawnMoves, dp);\n\n            // maximize as per alices\' strategy\n            maxAns = max(maxAns, moves + ans);\n        }\n        \n        return maxAns;\n    }\n};\n```
['Dynamic Programming', 'Game Theory', 'C++']