前言
又是好久没有更新了
正文
问题来源
本问题来自leetcode上的375题。（极小化极大问题）
问题描述
我们正在玩一个猜数游戏，游戏规则如下：
我从 1 到 n 之间选择一个数字，你来猜我选了哪个数字。
每次你猜错了，我都会告诉你，我选的数字比你的大了或者小了。
然而，当你猜了数字 x 并且猜错了的时候，你需要支付金额为 x 的现金。直到你猜到我选的数字，你才算赢得了这个游戏。
示例 :
n = 10, 我选择了8.
第一轮: 你猜我选择的数字是5，我会告诉你，我的数字更大一些，然后你需要支付5块。
第二轮: 你猜是7，我告诉你，我的数字更大一些，你支付7块。
第三轮: 你猜是9，我告诉你，我的数字更小一些，你支付9块。
游戏结束。8 就是我选的数字。
你最终要支付 5 + 7 + 9 = 21 块钱。
分析：
很遗憾的是我没能想到递推公式，看到官方题解才能写出。动态规划题若是想不出递推公式的话，是非常痛苦的；看到解答之后是豁然开朗的感觉。
dp(i,j) = min{pivot+max(dp(i,pivot-1),dp(pivot+1,j))} //pivot范围[i,j)；因为pivot为j时一定不是最小值
func max(a, b int) int {
if a > b {
return a
}
return b
}
func min(a, b int) int {
if a < b {
return a
}
return b
}
func getMoneyAmount(n int) int {
dp := make([][]int, n+1)
for i := 0; i <= n; i++ {
dp[i] = make([]int, n+1)
}
for size := 2; size <= n; size++ {
for i,j := 1, size; j <= n; {
tmp := math.MaxInt32
for k := i; k < j; k++ {
//tmp = min(tmp, )
res := k + max(dp[i][k-1], dp[k+1][j])
//fmt.Println(res)
tmp = min(res, tmp)
}
dp[i][j] = tmp
i++
j++
}
}
return dp[1][n]
}
//上述循环控制有两种，我偏向上面那种
for l := 0; l < n; l++ {
for i := 1; i <= n - l; i++ {
j := i + l
总结：
勤思考。
结语
不管怎么样好好加油。
