✅Beats 100% -08 Sept'24 Contest - Dynamic Programming- Explained in Detail
Intuition\n Describe your first thoughts on how to solve this problem. \nThe problem involves a turn-based game with two players (Alice and Bob) who move a knig
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nThe problem involves a turn-based game with two players (Alice and Bob) who move a knight on a chessboard to capture pawns. Alice aims to maximize the total number of moves made, while Bob aims to minimize it. Given that both players play optimally, we need to find the maximum number of moves Alice can ensure.\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n1. **Calculate Distances:** \n   - We first need to determine the number of moves it takes for the knight to reach each pawn from any given position. This can be calculated using Breadth-First Search (BFS) because the knight has specific move patterns and BFS is suitable for finding the shortest path in an unweighted grid.\n\n2. **Dynamic Programming on Subsets:**\n   - Use dynamic programming to solve the problem by considering all possible subsets of pawns and the state of the game at each subset. The state is defined by:\n     - `k`: the current pawn being considered.\n     - `curr`: the bitmask representing which pawns have been captured.\n     - `flag`: whose turn it is (Alice or Bob).\n   - The DP state `dp[k][curr]` represents the maximum (or minimum) number of moves from the state where the current pawn is `k` and the subset of captured pawns is `curr`.\n\n3. **Implementation Details:**\n   - **Distance Calculation (BFS):** Compute the shortest path from the knight\'s initial position to each pawn and between all pairs of pawns. This results in a distance matrix `d` where `d[i][j]` indicates the number of moves required to go from pawn `i` to pawn `j`.\n   - **Dynamic Programming Recursion:** Implement the DP recursion to handle the turn-based nature of the game. Alice tries to maximize the total moves while Bob tries to minimize them.\n\n\n# Complexity\n- Time complexity: `O(N x 2^N)`\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: `O(N x 2^N)`\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n\n\n# Example Breakdown\n\nConsider the example:\n- `kx = 0, ky = 2, positions = [[1,1],[2,2],[3,3]]`\n\n**Distance Calculation:**\n   - Use BFS to compute distances from the knight to each pawn and between pawns. For instance:\n     - Distance from `(0, 2)` to `(1, 1)` is 2 moves.\n     - Distance from `(0, 2)` to `(2, 2)` is 2 moves.\n     - Distance from `(0, 2)` to `(3, 3)` is 4 moves.\n     - And so on...\n\n**Dynamic Programming:**\n   - Initialize the DP table with the calculated distances.\n   - Recursively solve using the DP approach, alternating between Alice\u2019s and Bob\u2019s moves. \n\n### Summary\n\n- **Initialization:** Use BFS to compute shortest distances.\n- **DP Table:** Maintain and update the DP table based on current pawn and captured state.\n- **Final Computation:** Use the DP table to determine the maximum number of moves Alice can ensure.\n\nThis approach effectively combines BFS for distance calculations and DP for optimal turn-based play analysis to achieve the desired solution.\n\n# Code\n```java []\nclass Solution {\n\n    public int maxMoves(int kx, int ky, int[][] positions) {\n        HashMap<List<Integer>, Integer> map = new HashMap<>();\n        for (int i = 0; i < positions.length; i++) {\n            map.put(List.of(positions[i][0], positions[i][1]), i);\n        }\n        int[][] d = new int[positions.length + 1][positions.length + 1];\n        maxMoves(List.of(kx, ky), map, d[positions.length]);\n        for (int i = 0; i < positions.length; i++) {\n            maxMoves(List.of(positions[i][0], positions[i][1]), map, d[i]);\n        }\n        return maxMoves(positions.length, 0, d, true, new int[positions.length + 1][1 << positions.length]);\n    }\n\n    private void maxMoves(List<Integer> list, HashMap<List<Integer>, Integer> map, int[] d) {\n        ArrayDeque<List<Integer>> deque = new ArrayDeque<>(List.of(list));\n        HashSet<List<Integer>> set = new HashSet<>();\n        for (int i = 0, c = d.length; c > 1; i++) {\n            for (int j = deque.size(); j > 0; j--) {\n                List<Integer> poll = deque.poll();\n                if (!set.contains(poll)) {\n                    set.add(poll);\n                    if (map.containsKey(poll)) {\n                        d[map.get(poll)] = i;\n                        c--;\n                    }\n                    if (poll.get(0) >= 0 && poll.get(0) < 50 && poll.get(1) >= 0 && poll.get(1) < 50) {\n                        for (int[] k : new int[][] { { -2, -1 }, { -2, 1 }, { -1, -2 }, { -1, 2 }, { 1, -2 }, { 1, 2 }, { 2, -1 }, { 2, 1 } }) {\n                            deque.offer(List.of(poll.get(0) + k[0], poll.get(1) + k[1]));\n                        }\n                    }\n                }\n            }\n        }\n    }\n\n    private int maxMoves(int k, int curr, int[][] d, boolean flag, int[][] dp) {\n        if (curr + 1 == 1 << d.length - 1) {\n            return 0;\n        } else if (dp[k][curr] == 0) {\n            dp[k][curr] = flag ? 0 : Integer.MAX_VALUE;\n            for (int i = 0; i < d.length - 1; i++) {\n                if ((1 << i & curr) == 0) {\n                    int next = maxMoves(i, 1 << i | curr, d, !flag, dp) + d[k][i];\n                    dp[k][curr] = flag ? Math.max(dp[k][curr], next) : Math.min(dp[k][curr], next);\n                }\n            }\n        }\n        return dp[k][curr];\n    }\n}\n```\n![upvote.png](https://assets.leetcode.com/users/images/f68fcfb0-bf53-401e-a538-0f55657df911_1725769034.9801598.png)\n
['Dynamic Programming', 'Java']