LeetCode 375 - 猜数字大小 II

文章目录

• • 摘要
  • 描述
  • 题解答案
  • 题解代码分析
  • • 为什么这是区间 DP
    • DP 状态定义
    • Swift 可运行 Demo 代码
    • 代码为什么这样写
    • • 1. 为什么区间长度从小到大
      • 2. 为什么要 `max`
      • 3. 为什么不是二分
  • 示例测试及结果
  • 时间复杂度
  • 空间复杂度
  • 总结

摘要

LeetCode 375「猜数字大小 II」是一道典型的“看起来像二分，实际上是博弈 + 动态规划”的题。
很多人第一眼都会想：这不就是二分查找吗？
但一旦你真正开始算“最坏情况下要花多少钱”，就会发现这题完全不是在问“猜得快不快”，而是在问：

怎么猜，才能保证“无论对方选什么数字”，你都不会破产。

这个问题在真实世界里非常常见，比如：

• 风险对冲下的最坏成本评估
• 决策树里的最坏路径控制
• 不确定环境下的保底策略设计

这篇文章会从直觉思路一步步推导到标准解法，最后给出一份工程上稳定、好理解的 Swift 实现。

描述

游戏规则可以浓缩成一句话：

• 数字在[1, n]
• 你每猜错一次，就要为这次猜的数字付钱
• 对方会“诚实”告诉你是大了还是小了
• 你必须保证：不管对方选哪个数字，你都有钱赢

目标不是“平均花费最少”，而是：

在最倒霉的情况下，你最少需要准备多少钱，才能稳赢。

这一点非常关键，它直接决定了我们要用的是：

• 最坏情况（max）
• 而不是期望值或平均值

题解答案

核心思想一句话总结：

对每个区间[l, r]，枚举第一次猜的数字k，取“左右区间最坏情况中的较大值”，再加上k本身的成本，最终取最小的那个k。

听起来有点绕，我们拆开说。

题解代码分析

为什么这是区间 DP

假设当前要猜的范围是[l, r]。

你如果第一次猜k：

• 猜对了：花费0

• 猜错了：

  • 数字在[l, k-1]
  • 或[k+1, r]
  • 你要面对的是更糟的那一边

所以成本是：

k + max( cost(l, k-1), cost(k+1, r) )

我们的目标是：
在[l, r]里选一个k，让这个值尽可能小。

DP 状态定义

dp[l][r] = 在区间 [l, r] 内，保证获胜所需的最小现金

边界条件：

• l >= r：不需要猜，花费0

状态转移：

dp[l][r] = min over k in [l, r] ( k + max(dp[l][k-1], dp[k+1][r]) )

Swift 可运行 Demo 代码

classSolution{funcgetMoneyAmount(_n:Int)->Int{ifn<=1{return0}// dp[l][r] 表示在区间 [l, r] 内保证赢所需的最小花费vardp=Array(repeating:Array(repeating:0,count:n+2),count:n+2)// 区间长度从 2 开始ifn>=2{forlenin2...n{forlin1...n-len+1{letr=l+len-1dp[l][r]=Int.maxforkinl...r{letcost=k+max(k-1>=l?dp[l][k-1]:0,k+1<=r?dp[k+1][r]:0)dp[l][r]=min(dp[l][r],cost)}}}}returndp[1][n]}}

代码为什么这样写

1. 为什么区间长度从小到大

因为：

• dp[l][r]依赖dp[l][k-1]和dp[k+1][r]
• 它们的区间一定比[l, r]小

这就是典型的区间 DP 填表顺序。

2. 为什么要max

因为你不是在和一个“善良的系统”博弈，而是在和一个最坏情况博弈。

对方一定会让你走最贵的那条路。

3. 为什么不是二分

二分是为了减少猜测次数，
而这道题是为了控制最坏成本。

这两者在很多区间上并不一致。

示例测试及结果

letsolution=Solution()print(solution.getMoneyAmount(1))// 0print(solution.getMoneyAmount(2))// 1print(solution.getMoneyAmount(10))// 16

输出结果：

0 1 16

和题目示例完全一致。

时间复杂度

三层循环：

• 区间长度：O(n)
• 左端点：O(n)
• 枚举猜测点：O(n)

总体时间复杂度：

O(n³)

在n <= 200的限制下，这是完全可接受的。

空间复杂度

使用了一个(n+2) x (n+2)的 DP 表：

O(n²)

空间换稳定性，非常值得。

总结

LeetCode 375 是一道非常标准的“最坏情况决策问题”：

• 它不是考你猜得聪不聪明
• 而是考你是否考虑到了所有不利情况

这类题在真实工程中非常常见，比如：

• 风控系统里的最大损失评估
• 自动化决策中的保底策略
• 游戏 AI 的最坏路径规划

如果你能把这道题的 DP 推清楚，其实你已经掌握了一大类博弈型区间 DP 的通用套路。