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
}