[Python] simple top-down dp solution - O(N^4)
Idea\n\ndp(l, r, m) is the result when firstPlayer is the l-th player from left and secondPlayer is the r-th player from right, and there are m players in total
**Idea**\n\n`dp(l, r, m)` is the result when firstPlayer is the `l-th` player from left and secondPlayer is the `r-th` player from right, and there are `m` players in total.\n\nThe base case is straight-forward: simply check `l == r`. \n\nBy making sure `l <= r`, the dp transition is also manageable. In the next round, `l` can be `1, ..., l`. The only tricky part is the range of `r` in the next round. This depends on two things:\n1) how many times the players to the left of first player win/lose. \n2) the second player is in the left or right half of the remaining players. \n\nPlease see code below for more details =)\n\n</br>\n\n**Complexity**\n\nFor `dp(l, r, m)`, `l` and `r` are of `O(N)`, and `m` is of `O(logN)`. The loop in `dp` takes `O(M^2)`. \n\nBased on [@DBabichev](https://leetcode.com/DBabichev/)\'s comment, there are in total `n^2 + (n//2)^2 + ...` states, so the total time complexity is `O(N^4)`.\n\n- Time complexity: `O(N^4)`\n- Space complexity: `O(N^2)`\n\n</br>\n\n**Python**\n\n```Python\nclass Solution:\n    def earliestAndLatest(self, n: int, firstPlayer: int, secondPlayer: int) -> List[int]:\n        @cache\n        def dp(l, r, m):\n            # make sure l <= r\n            if l > r:\n                return dp(r, l, m)\n            # base case\n            if l == r:\n                return (1, 1)\n            # dp transition\n            nxt_m = (m + 1) // 2\n            ans = [n, 0]\n            for i in range(1, l + 1):\n                l_win, l_lose = i - 1, l - i\n                for j in range(max(r - (m//2) - 1, 0) + l_lose + 1, min(r - 1 - l_win, nxt_m - i) + 1):\n                    tmp = dp(i, j, nxt_m)\n                    ans = min(ans[0], tmp[0]), max(ans[1], tmp[1])\n            return (ans[0] + 1, ans[1] + 1)\n        \n        return dp(firstPlayer, n - secondPlayer + 1, n)\n```
[]