为什么很多人刷不会《猜数字大小 II》？不是不会二分，而是没看懂“最坏情况”——一文彻底吃透动态规划

为什么很多人刷不会《猜数字大小 II》？不是不会二分，而是没看懂“最坏情况”——一文彻底吃透动态规划

大家好，我是Echo_Wish。

很多人第一次刷到 LeetCode 的《猜数字大小 II（Guess Number Higher or Lower II）》时，第一反应往往是：

这不就是二分查找吗？

结果提交之后，Wrong Answer。

然后开始怀疑人生：

二分不是每次猜中间数字最快吗？

遗憾的是，这道题恰恰就是来"打脸二分"的。

它告诉我们一个非常重要的算法思想：

最快，不代表代价最小；平均最好，也不代表最坏最好。

这也是动态规划里非常经典的一类问题——极小化最大损失（Minimax DP）。

今天，我们就一起彻底搞懂这道经典面试题。

一、先理解题目到底在说什么

题目大概意思如下：

现在有一个数字。

范围：

1 ~ n