Leetcode: Guess Number Higher or Lower II

Guess Number Higher or Lower

Similar Problems:

We are playing the Guess Game. The game is as follows:

I pick a number from 1 to n. You have to guess which number I picked.

Every time you guess wrong, I’ll tell you whether the number I picked is higher or lower.

However, when you guess a particular number x, and you guess wrong, you pay $x. You win the game when you guess the number I picked.


n = 10, I pick 8.

First round:  You guess 5, I tell you that it's higher. You pay $5.
Second round: You guess 7, I tell you that it's higher. You pay $7.
Third round:  You guess 9, I tell you that it's lower. You pay $9.

Game over. 8 is the number I picked.

You end up paying $5 + $7 + $9 = $21.

Given a particular n >= 1, find out how much money you need to have to guarantee a win.

Github: code.dennyzhang.com

Credits To: leetcode.com

Leave me comments, if you have better ways to solve.

// Blog link: https://code.dennyzhang.com/guess-number-higher-or-lower-ii
// Basic Ideas: Dynamic Programming
// f(i, j) -> money we need to gurantee a win for the range of [i, j]
//    We will have to start by picking one, let's say it's k.
//    Then the cost is: k + max(f(i, k-1), f(k+1, j))
// From bottom to up, from left to right, we can get f(1, n)
// Complexity: Time O(n*n*n), Space O(n*n)
func getMoneyAmount(n int) int {
    dp := make([][]int, n+1)
    for i:=0; i<n+1; i++ { dp[i] = make([]int, n+1) }
    for i:=n-1; i>=1; i-- {
        // Range of i:j
        for j := i+1; j<=n; j++ {
            cost, mincost := 0, 1<<31 - 1
            for k:=i; k<=j; k++ {
                cost = k
                r1, r2 := 0, 0
                if k!=i { r1 = dp[i][k-1] }
                if k!=j { r2 = dp[k+1][j] }
                if r1 > r2 {
                    cost += r1
                } else {
                    cost += r2
                if mincost > cost { mincost = cost }
            dp[i][j] = mincost
    return dp[1][n]

Share It, If You Like It.

Leave a Reply

Your email address will not be published.