# Python solution with detailed explanation

• 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]

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