Solution
Guess Number Higher or Lower II https://leetcode.com/problems/guessnumberhigherorlowerii/
 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,k1] 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, k1, cache), self.cost(k+1, hi, cache))+k)
 Using the above key idea, we realize that this problem can be parameterized by lo and hi. When lo = hi, the cost is 0 since we can make just a single guess which will be correct. The case hi < lo will be an invalid case and hence we return zero for that as well.
 https://discuss.leetcode.com/topic/51494/javacommenteddpsolution
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, k1, 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/(hilo+1)

1p: Probability that k is not the right choice = (hilo)/(hilo+1)

cost[lo, hi] = min(p*cost_success(k) + (1p)*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, k1] with probability p_1ower or [k+1, hi] with probability p_higher. p_1ower = (klo)/(hilo+1) and p_higher = (hik)/(hilo+1).

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

cost[lo, hi] = min((1p)((cost[lo,k  1] + k)((klo)/(hilo+1)) + (cost[k+1,hi] + k)*((hik)/(hilo+1)))) where k is between [lo, hi]