Java DFS solution. O(2^N/2 * N/2)
First of all, why is this not a DP. Because there are no recurring sub problems. Each state is different.\nBecause, whenever a chosen player plays, they definit
First of all, why is this not a DP. Because there are no recurring sub problems. Each state is different.\nBecause, whenever a chosen player plays, they definitely win. For every other player, we have 2 options, they win or they lose. Although this part looks like a DP, these never make us do recurring sub-problems. The reason for that is whenever someone plays, the opposing player\'s choice is already made, which leads to a different part of the decision tree. \n```\nclass Solution \n{\n    int firstPlayer,secondPlayer,n;\n    boolean enumerate(ArrayList<Integer> ret,int mask,int start,int end)\n    {\n        if(start>=end)\n        {\n            ret.add(mask);\n            return false;\n        }\n        else\n        {\n            while((start<end)&&((mask&(1<<start))!=0))\n                start++;\n            while((start<end)&&((mask&(1<<end))!=0))\n                end--;\n            if(start>=end)\n                return enumerate(ret,mask,start+1,end-1);\n            else if(start==firstPlayer&&end==secondPlayer)\n                    return true;\n            else if(start==firstPlayer||start==secondPlayer)\n                return enumerate(ret,mask|1<<end,start+1,end-1);\n            else if(end==firstPlayer||end==secondPlayer)\n                return enumerate(ret,mask|1<<start,start+1,end-1);\n            else return enumerate(ret,mask|1<<start,start+1,end-1)||enumerate(ret,mask|1<<end,start+1,end-1);\n                \n        }\n    }\n    int minDFS(int mask)\n    {\n        int start=0,end=n-1;\n        ArrayList<Integer> arr=new ArrayList<Integer>();\n        if(enumerate(arr,mask,start,end))\n            return 1;\n        else\n        {\n            int q=Integer.MAX_VALUE;\n            for(int x:arr)\n                q=Math.min(q,1+minDFS(x));\n            return q;\n        }\n    } \n    int maxDFS(int mask)\n    {\n        int start=0,end=n-1;\n        ArrayList<Integer> arr=new ArrayList<Integer>();\n        if(enumerate(arr,mask,start,end))\n            return 1;\n        else\n        {\n            int q=Integer.MIN_VALUE;\n            for(int x:arr)\n                q=Math.max(q,1+maxDFS(x));\n            return q;\n        }\n    }\n\n    public int[] earliestAndLatest(int n, int firstPlayer, int secondPlayer) \n    {\n        this.n=n;\n        this.firstPlayer=firstPlayer-1;\n        this.secondPlayer=secondPlayer-1;\n        return new int[]{minDFS(0),maxDFS(0)};        \n    }\n}\n```
['Depth-First Search', 'Java']