Guess Number Higher or Lower II LeetCode solution in Python

1
class Solution:
2
    def getMoneyAmount(self, n):
3
        # For an interval [l,r], we choose a num, which if incorrect still
4
        # allows us to know whether the secret# is in either [l,num-1] or
5
        # [num+1,r]. So, the worst-case (w-c) cost is
6
        #
7
        #      num + max(w-c cost in [l,num-1], w-c cost in [num+1,r])
8
        #
9
        # We do this by recursion and binary search, starting with [1,n].
10

11
        @lru_cache(None)  # <-- we cache function results to avoid recomputing them
12
        def dp(l=1, r=n) -> int:
13
            if r - l < 1:
14
                return 0  # <-- base case for the recursion; one number in [l,r]
15
            ans = 1000  # <-- the answer for n = 200 is 952
16

17
            for choice in range((l + r) // 2, r):
18
                ans = min(ans, choice + max(dp(l, choice - 1), dp(choice + 1, r)))
19

20
            return ans
21

22
        return dp()