Python solution with detailed explanation


  • 0
    G

    Solution

    Guess Number Higher or Lower II https://leetcode.com/problems/guess-number-higher-or-lower-ii/

    • The key idea in this problem is that given any n, we make a guess for k. Then we break the interval [1,n] into [1,k-1] and [k+1,n]. The minimum of the worst case cost can be calculated recursively as: cost[1,n] = k + max{cost[1,k - 1] + cost[k+1,n]}.
            for k in range(lo, hi+1):
                cache[lo][hi] = min(cache[lo][hi], max(self.cost(lo, k-1, cache), self.cost(k+1, hi, cache))+k)
    
    class Solution(object):
        def cost(self, lo, hi, cache):
            if hi <= lo:
                return 0
            if cache[lo][hi] != float('inf'):
                return cache[lo][hi]
            for k in range(lo, hi+1):
                cache[lo][hi] = min(cache[lo][hi], max(self.cost(lo, k-1, cache), self.cost(k+1, hi, cache))+k)
            return cache[lo][hi]
        
        def getMoneyAmount(self, n):
            """
            :type n: int
            :rtype: int
            """
            cache = [[float('inf')]*(n+1) for _ in range(n+1)]
            return self.cost(1, n, cache)
    

    Expected Loss

    • p: Probability that k is the right choice = 1/(hi-lo+1)

    • 1-p: Probability that k is not the right choice = (hi-lo)/(hi-lo+1)

    • cost[lo, hi] = min(p*cost_success(k) + (1-p)*cost_failure(k)) where k is between [lo, hi]

    • Now cost_success(k) = 0. When we have a failure, the answer can lie between [lo, k-1] with probability p_1ower or [k+1, hi] with probability p_higher. p_1ower = (k-lo)/(hi-lo+1) and p_higher = (hi-k)/(hi-lo+1).

    • cost_failure(k) = (cost[lo,k - 1] + k)*p_1ower + (cost[k+1,hi] + k)*p_higher

    • cost[lo, hi] = min((1-p)((cost[lo,k - 1] + k)((k-lo)/(hi-lo+1)) + (cost[k+1,hi] + k)*((hi-k)/(hi-lo+1)))) where k is between [lo, hi]


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.