# 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.

Example:

```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[n]
}
```

Share It, If You Like It.