1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
| // @Title: 猜数字大小 II (Guess Number Higher or Lower II)
// @Author: 15816537946@163.com
// @Date: 2021-11-12 19:29:26
// @Runtime: 16 ms
// @Memory: 4.8 MB
func getMoneyAmount(n int) int {
dp := make([][]int, n+1)
for i, _ := range dp {
dp[i] = make([]int, n+1)
}
for diff := 1; diff < n; diff++ {
for i := 1; i <= n-diff; i++ {
j := i + diff
dp[i][j] = j * j
for k := i; k < j; k++ {
dp[i][j] = min(dp[i][j], max(dp[i][k-1], dp[k+1][j])+k)
}
}
}
return dp[1][n]
}
func min(a, b int) int {
if a > b {
return b
}
return a
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
|