Java | Top-Down DP | Nested Recursion | Comments
This recursion has 2 layers. The top layer is for choosing whether the right or left player wins, the bottom layer is for advancing the round.\n\nI only memo th
This recursion has 2 layers. The top layer is for choosing whether the right or left player wins, the bottom layer is for advancing the round.\n\nI only memo the round layer and it is good enough.\n\nIt reminds me of some DP medium questions which can also be solved this way. The num of ways to stack the brick one and a few others.\n```Java\nclass Solution {\n    public int[] earliestAndLatest(int n, int firstPlayer, int secondPlayer) {\n        return solve(n, (1<<n)-1, 0, n-1, firstPlayer-1, secondPlayer-1, new HashMap<>());\n    }\n\n    private int[] solve(int n, int mask, int lo, int hi, int a, int b, Map<Integer, int[]> map){\n        while((mask&1<<hi)==0){ // find the next set bit for hi\n            hi--;\n        }\n        while((mask&1<<lo)==0){ // find the next set bit for lo\n            lo++;\n        }\n        if (lo>=hi){ // if the round ends, advance to the next layer "anew"\n            if (map.containsKey(mask)){ // if we\'ve seen it, just return it.\n                return map.get(mask);\n            }\n            int[] res = solve(n, mask, 0, n-1, a, b, map);\n            res[0]++; res[1]++;\n            map.put(mask, res);\n            return res;\n        }\n        if (lo==a&&hi==b||lo==b&&hi==a){ // oops, it ends here.\n            return new int[]{1, 1};\n        }\n        int[] ans = new int[]{100, 0};\n        if (hi!=a&&hi!=b){ // make hi lose \n            int[] x = solve(n, mask^1<<hi, lo+1, hi-1, a, b, map);\n            ans[0] = Math.min(ans[0], x[0]);\n            ans[1] = Math.max(ans[1], x[1]);\n        }\n        if (lo!=a&&lo!=b){ // make lo lose\n            int[] y = solve(n, mask^1<<lo, lo+1, hi-1, a, b, map);\n            ans[0] = Math.min(ans[0], y[0]);\n            ans[1] = Math.max(ans[1], y[1]);\n        }\n        return ans;\n    }\n}\n```
['Java']