本文共 1113 字，大约阅读时间需要 3 分钟。
为了解决这个问题，我们需要找到在猜数字游戏中确保胜利所需的最小金额。每次猜测错误时，玩家会支付猜测的数字。目标是通过优化猜测策略，尽可能减少支付的总金额。
我们可以使用动态规划来解决这个问题。定义 dp[i][j] 表示在区间 [i, j] 中，玩家需要支付的最小金额。我们从较小的区间开始，逐步计算到较大的区间。
dp[i][i] = 0。[i, j]，选择中间的数 mid 作为猜测点。支付 mid 后，进入左右子区间 [i, mid-1] 或 [mid+1, j]，选择支付较少的方案。因此，递推公式为：[dp[i][j] = mid + \min(dp[i][mid-1], dp[mid+1][j])]其中 mid = (i + j) / 2。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]; }} dp，其中 dp[i] 表示区间 [i, i] 的支付金额，初始值为 i。[i, j] 的最小支付金额。选择中间的数 mid，并计算左右子区间的最小值，更新 dp[i][j]。dp[1][n] 表示整个区间 [1, n] 的最小支付金额。通过这种动态规划的方法，我们可以高效地计算出确保胜利所需的最小金额。
转载地址：http://yngfk.baihongyu.com/