## Dynamic Programming - 375. Guess Number Higher or Lower II

Updated on with 0 views and 0 comments

375. Guess Number Higher or Lower II

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.

go :

``````func getMoneyAmount(n int) int {
var dp = make([][]int, n+1)
for i := range dp {
dp[i] = make([]int, n+1)
}

for j := 2; j <= n; j++ {
for i := j-1; i > 0; i-- {
globalMin :=math.MaxInt32
for k := i+1; k < j; k++ {
localMax := k + max(dp[i][k-1], dp[k+1][j])
globalMin = min(globalMin, localMax)
}
if i+1 == j {
dp[i][j] = i
} else {
dp[i][j] = globalMin
}
}
}

return dp[1][n];
}

// recursive dp solution
func getMoneyAmount(n int) int {

var dp = make([][]int, n+1)
for i := range dp {
dp[i] = make([]int, n+1)
}

return dfs(1, n, &dp)
}

func dfs(start, end int, dp *[][]int) int {
if start >= end {
return 0
}
if (*dp)[start][end] != 0 {
return (*dp)[start][end]
}

res := math.MaxInt32
for i := start; i <= end; i++ {
res = min(res, i + max(dfs(start, i - 1, dp), dfs(i + 1, end, dp)))
}

(*dp)[start][end] = res

return res;
}

func min(i, j int) int {
if i < j {
return i
}
return j
}

func max(i, j int) int {
if i > j {
return i
}
return j
}
``````