[LeetCode] 375. Guess Number Higher or Lower II

 Problem: https://leetcode.com/problems/guess-number-higher-or-lower-ii/

Need to find the minimal cost among all worst scenarios ( wrong guesses ).

For a sorted section [low, high]:

If the pivot < low + (high - low) // 2, the worst scenario cost of left section always less than the cost of right section.  Because numbers in section are in ascending order and the left section has less numbers than right sections.

It is safe to start the pivot from the middle position ( low + (high - low) // 2 ).

class Solution:
    def getMoneyAmount(self, n: int) -> int:
        
        @lru_cache(maxsize = None)
        def helper(low, high):
            if low >= high:
                return 0
            
            result = 2**31 - 1 # MAX_INT
            for i in range(low + (high - low)//2, high+1):
                # cost of picking number i (wrong guess) + worst scenario one left / right sections
                cost = i + max(helper(low,i-1), helper(i+1,high))
                # minimal cost among all worst scenarios
                result = min(result, cost)
            
            return result
        
        return helper(1, n)