[C++] DP Explained In-Depth - Beats 100% Time + Space
Performance\nJustifying the title. This runs in 555ms and uses 91.25MB memory. The top buckets I see on the leaderboard run in 1436ms and use 231.7MB memory. \n
# Performance\nJustifying the title. This runs in 555ms and uses 91.25MB memory. The top buckets I see on the leaderboard run in 1436ms and use 231.7MB memory. \n\nI usually see 100% when I submit code in rust and theres few solutions, I wouldn\'t be surprised if thats the case here and this goes down over time, but I\'m pretty proud of getting 100% in both categories with a C++ submission!\n\n# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nThis problem uses Mini-Max, ie one minimising player followed by one maximising player, the mini-max algorithm is implemented recursively and lends itself to dynamic programming.\n\nWe can iterate over 15 positions quickly, but calculating the cost might be more difficult. To pre-calculate a move between any two positions would mean $50\\times50$ starting positions to $50\\times50$ ending positions, which is $50^4=6,250,000$. That\'s too much for leetcode, usually the limit is over $100,000$ but less than $1,000,000$. But, if we just re-center the board around our knight ,we can precalculate all moves.\n\nThe number of moves to reach any given position follows an interesting pattern.\n```\n8 7 6 7 6 5 6 5 6 5 6 5 6 5 6 5 6 7 6 7 8 \n7 6 7 6 5 6 5 6 5 6 5 6 5 6 5 6 5 6 7 6 7 \n6 7 6 5 6 5 4 5 4 5 4 5 4 5 4 5 6 5 6 7 6 \n7 6 5 6 5 4 5 4 5 4 5 4 5 4 5 4 5 6 5 6 7 \n6 5 6 5 4 5 4 3 4 3 4 3 4 3 4 5 4 5 6 5 6 \n5 6 5 4 5 4 3 4 3 4 3 4 3 4 3 4 5 4 5 6 5 \n6 5 4 5 4 3 4 3 2 3 2 3 2 3 4 3 4 5 4 5 6 \n5 6 5 4 3 4 3 2 3 2 3 2 3 2 3 4 3 4 5 6 5 \n6 5 4 5 4 3 2 3 4 1 2 1 4 3 2 3 4 5 4 5 6 \n5 6 5 4 3 4 3 2 1 2 3 2 1 2 3 4 3 4 5 6 5 \n6 5 4 5 4 3 2 3 2 3 0 3 2 3 2 3 4 5 4 5 6 \n5 6 5 4 3 4 3 2 1 2 3 2 1 2 3 4 3 4 5 6 5 \n6 5 4 5 4 3 2 3 4 1 2 1 4 3 2 3 4 5 4 5 6 \n5 6 5 4 3 4 3 2 3 2 3 2 3 2 3 4 3 4 5 6 5 \n6 5 4 5 4 3 4 3 2 3 2 3 2 3 4 3 4 5 4 5 6 \n5 6 5 4 5 4 3 4 3 4 3 4 3 4 3 4 5 4 5 6 5 \n6 5 6 5 4 5 4 3 4 3 4 3 4 3 4 5 4 5 6 5 6 \n7 6 5 6 5 4 5 4 5 4 5 4 5 4 5 4 5 6 5 6 7 \n6 7 6 5 6 5 4 5 4 5 4 5 4 5 4 5 6 5 6 7 6 \n7 6 7 6 5 6 5 6 5 6 5 6 5 6 5 6 5 6 7 6 7 \n8 7 6 7 6 5 6 5 6 5 6 5 6 5 6 5 6 7 6 7 8 \n```\nYou can see the 0 in the middle as the starting position, each number here represents the required number of moves to reach the position. I played around visualising this at first, but ultimately rather than hand-calculate it or figure out a clever trick, I just decided to pre-calculate a $101\\times101$ board with all these figures, which is what the `bfs()` function returns. (I\'m pretty sure this could be `constexpr` meaning calculated at compile time, but leetcode doesn\'t like that).\n\nNow, there is only one edge case. If you are in a corner, and the pawn is diagonally adjacent to you, you need an extra two moves.\n\n![corner_000.png](https://assets.leetcode.com/users/images/d71e274f-4b98-4f36-9cde-8c6a2a8cf756_1725857664.207959.png)\n\n\nHere, I\'ve highlighted all good paths the knight could take. It could read the pawn from the two out-of-bounds $1$-move positions, but thats illegal. Instead, it must traverse to one of the $3$-move positions before it can reach the pawn.\n\nOh, and it doesn\'t matter if you switch the positions of the pawn and the knight. Think about it.\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\nThe `bfs` function will map each position to the required number of moves to reach it from $(50, 50)$. This is then stored in a static variable in `moves_to`, which means it is only initialised once, rather than re-calculated every time. This means every time we want to check the cost of a move, it occurs in constant time. The `moves_to` function also deals with the corner edge-case.\n\nOur mini-max DFS is otherwise pretty standard except for the dp. I decided to use a bitmask to represent the state of visited positions. This takes 15 bits, for each state. However, even if we\'ve captured a given set of pawns, our state might differ based on current position, hence this is also incorporated into the key in the dp map. Since `kx` and `ky` are less than 50, it only takes an extra 6 bits to store these, so we can just shift them over and store them in the same integer, which is then used as a key.\n\nWhen iterating through pawns to take, we only look at those we haven\'t previously taken.\n\n# Complexity\n- Time complexity: $$O(n^2 \\times 2^n)$$\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: $$O(n \\times 2^n)$$\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n$n$ represents the number of pawns, and is at most $15$. $15 \\times 2^15 = 491,520$.\n\nThe $n^2$ comes cos for each position we iterate through all the pawns we could possibly taken, even if we skip them. That extra factor of 15 could just prevent this algorithm from working, but I suppose its fast enough that this still runs, even in 500ms+.\n\n\n# Code\n```cpp []\nstruct State {\n    int mask;\n    int x;\n    int y;\n};\n\nauto bfs() -> array<array<int, 101>, 101> {\n    array<array<int, 101>, 101> ans = {0};\n    vector<vector<bool>> visited(101, vector(101, false));\n\n    // current position: 50, 50\n    queue<tuple<int, int, int>> q;\n    q.emplace(50, 50, 0);\n    while (!q.empty()) {\n        auto [x, y, moves] = q.front();\n        q.pop();\n        if (x < 0 || y < 0 || x >= ans.size() || y >= ans.size()) continue;\n        if (visited[x][y]) continue;\n        ans[x][y] = moves;\n        visited[x][y] = true;\n        q.emplace(x+1, y+2, moves+1);\n        q.emplace(x+1, y-2, moves+1);\n        q.emplace(x-1, y+2, moves+1);\n        q.emplace(x-1, y-2, moves+1);\n        q.emplace(x+2, y+1, moves+1);\n        q.emplace(x-2, y+1, moves+1);\n        q.emplace(x+2, y-1, moves+1);\n        q.emplace(x-2, y-1, moves+1);\n    }\n\n    return ans;\n};\n\nclass Solution {\npublic:\n    unordered_map<int, int> dp;\n    span<vector<int>> positions;\n    int final_state;\n\n    int f(State state, bool minimising) {\n        if (state.mask == final_state) return 0;\n        int key = state.mask | (state.x << 16) | (state.y << 22);\n        if (dp.contains(key)) return dp[key];\n\n        int ans = minimising ? INT_MAX : INT_MIN;\n\n        for (int i = 0; i < positions.size(); ++i) {\n            int new_mask = state.mask | (1 << i);\n            if (new_mask == state.mask) continue;\n            int x = positions[i][0], y = positions[i][1];\n            State new_state{new_mask, x, y};\n            int res = f(new_state, !minimising) \n                + moves_to(state.x, state.y, new_state.x, new_state.y);\n            ans = minimising ? min(ans, res) : max(ans, res);\n        }\n\n        return dp[key] = ans;\n    }\n\n    int maxMoves(int kx, int ky, span<vector<int>> pos) {\n        State state{0, kx, ky};\n        this->positions = pos;\n        this->final_state = (1 << positions.size()) - 1;\n        return f(state, false);\n    }\n\n    int moves_to(int kx, int ky, int x, int y) {\n        bool corner = false;\n        corner = corner || (kx == 0 && ky == 0) || (x == 0 && y == 0);\n        corner = corner || (kx == 49 && ky == 0) || (x == 49 && y == 0);\n        corner = corner || (kx == 49 && ky == 49) || (x == 49 && y == 49);\n        corner = corner || (kx == 0 && ky == 49) || (x == 0 && y == 49);\n        \n        if (corner && abs(kx-x) == 1 && abs(ky-y) == 1) {\n            return 4;\n        }\n\n        static auto dp = bfs();\n\n        return dp[50+(x-kx)][50+(y-ky)];\n    }\n\n};\n    \n\n```
['C++']