State: current mouse index and bitmask representing assigned holes
For each mouse, try assigning it to each unassigned hole
Recursively solve for remaining mice and holes
Return the minimum of maximum distances across all possible assignments
Base case: when all mice are assigned, return 0
Code

[{"language":"C++","code":"class Solution {\nprivate:\n    unordered_map<string, int> memo;\n    \npublic:\n    int assignMiceDP(vector<int>& mice, vector<int>& holes) {\n        memo.clear();\n        return dp(0, 0, mice, holes);\n    }\n    \nprivate:\n    int dp(int mouseIdx, int mask, vector<int>& mice, vector<int>& holes) {\n        if (mouseIdx == mice.size()) {\n            return 0;\n        }\n        \n        string key = to_string(mouseIdx) + \",\" + to_string(mask);\n        if (memo.find(key) != memo.end()) {\n            return memo[key];\n        }\n        \n        int result = INT_MAX;\n        for (int i = 0; i < holes.size(); i++) {\n            if (!(mask & (1 << i))) {  // hole i is not assigned\n                int dist = abs(mice[mouseIdx] - holes[i]);\n                int nextResult = dp(mouseIdx + 1, mask | (1 << i), mice, holes);\n                result = min(result, max(dist, nextResult));\n            }\n        }\n        \n        return memo[key] = result;\n    }\n};","lang":"cpp","html":"<pre class=\"shiki shiki-themes github-light github-dark\" style=\"background-color:#fff;--shiki-dark-bg:#24292e;color:#24292e;--shiki-dark:#e1e4e8\" tabindex=\"0\"><code><span class=\"line\"><span style=\"color:#D73A49;--shiki-dark:#F97583\">class</span><span style=\"color:#6F42C1;--shiki-dark:#B392F0\"> Solution</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\"> {</span></span>\n<span class=\"line\"><span style=\"color:#D73A49;--shiki-dark:#F97583\">private:</span></span>\n<span class=\"line\"><span style=\"color:#24292E;--shiki-dark:#E1E4E8\">    unordered_map</span><span style=\"color:#D73A49;--shiki-dark:#F97583\">&#x3C;</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\">string, </span><span style=\"color:#D73A49;--shiki-dark:#F97583\">int></span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\"> memo;</span></span>\n<span class=\"line\"><span style=\"color:#24292E;--shiki-dark:#E1E4E8\">    </span></span>\n<span class=\"line\"><span style=\"color:#D73A49;--shiki-dark:#F97583\">public:</span></span>\n<span class=\"line\"><span style=\"color:#D73A49;--shiki-dark:#F97583\">    int</span><span style=\"color:#6F42C1;--shiki-dark:#B392F0\"> assignMiceDP</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\">(</span><span style=\"color:#6F42C1;--shiki-dark:#B392F0\">vector</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\">&#x3C;</span><span style=\"color:#D73A49;--shiki-dark:#F97583\">int</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\">></span><span style=\"color:#D73A49;--shiki-dark:#F97583\">&#x26;</span><span style=\"color:#E36209;--shiki-dark:#FFAB70\"> mice</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\">, </span><span style=\"color:#6F42C1;--shiki-dark:#B392F0\">vector</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\">&#x3C;</span><span style=\"color:#D73A49;--shiki-dark:#F97583\">int</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\">></span><span style=\"color:#D73A49;--shiki-dark:#F97583\">&#x26;</span><span style=\"color:#E36209;--shiki-dark:#FFAB70\"> holes</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\">) {</span></span>\n<span class=\"line\"><span style=\"color:#24292E;--shiki-dark:#E1E4E8\"
Related Tags
