375. 猜数字大小 II 难

375. 猜数字大小 II

我们正在玩一个猜数游戏，游戏规则如下：
我从 1 到 n 之间选择一个数字，你来猜我选了哪个数字。
每次你猜错了，我都会告诉你，我选的数字比你的大了或者小了。
然而，当你猜了数字 x 并且猜错了的时候，你需要支付金额为 x 的现金。直到你猜到我选的数字，你才算赢得了这个游戏。

//错误方法，二分
func getMoneyAmount(n int) int {
    left, right, guess, result := 1, n, n, 0
    for left <= right {
        mid := left + (right-left)/2
        if mid == guess {
            return result
        } else if mid < guess {
            left = mid + 1
        } else {
            right = mid - 1
        }
        result += mid
    }
    return result
}

//实际考察动态规划
func getMoneyAmount(n int) int {
    dp := make([][]int, n+1)
    for k := range dp {
        dp[k] = make([]int, n+1)
    }
    for l := 2; l <= n; l++ {
        for left := 1; left+l-1 <= n; left++ {
            minValue := math.MaxInt32
            right := left + l - 1
            for piv := left; piv < right; piv++ {
                minValue = min(minValue, piv+max(dp[left][piv-1], dp[piv+1][right]))
            }
            dp[left][right] = minValue
        }
    }
    return dp[1][n]
}

func max(num1, num2 int) int {
    if num1 > num2 {
        return num1
    }
    return num2
}

func min(num1, num2 int) int {
    if num1 < num2 {
        return num1
    }
    return num2
}

//回溯法优化
var memo map[string]int

func getMoneyAmount(n int) int {
    memo = make(map[string]int)
    return dfs(1, n)
}

func dfs(left, right int) int {
    key := fmt.Sprintf("%d-%d", left, right)
    if value, ok := memo[key]; ok {
        return value
    }
    if left >= right {
        return 0
    }
    result := math.MaxInt32
    for i := left; i <= right; i++ {
        result = min(result, i+max(dfs(left, i-1), dfs(i+1, right)))
    }
    memo[key] = result
    return result
}

func max(num1, num2 int) int {
    if num1 > num2 {
        return num1
    }
    return num2
}

func min(num1, num2 int) int {
    if num1 < num2 {
        return num1
    }
    return num2
}