本文共 1113 字，大约阅读时间需要 3 分钟。

为了解决这个问题，我们需要找到在猜数字游戏中确保胜利所需的最小金额。每次猜测错误时，玩家会支付猜测的数字。目标是通过优化猜测策略，尽可能减少支付的总金额。

方法思路

我们可以使用动态规划来解决这个问题。定义 dp[i][j] 表示在区间 [i, j] 中，玩家需要支付的最小金额。我们从较小的区间开始，逐步计算到较大的区间。

解决代码

public class Solution {    public int getMoneyAmount(int n) {        if (n == 1) return 0;        if (n == 2) return 1;        int[] dp = new int[n + 1];        for (int i = 1; i <= n; i++) {            dp[i] = i;        }        for (int length = 3; length <= n; length++) {            for (int i = 1; i <= n - length + 1; i++) {                int j = i + length - 1;                int mid = (i + j) / 2;                dp[i][j] = mid + Math.min(dp[i][mid - 1], dp[mid + 1][j]);            }        }        return dp[1][n];    }}

代码解释

通过这种动态规划的方法，我们可以高效地计算出确保胜利所需的最小金额。