为什么很多人刷不会《猜数字大小 II》？不是不会二分，而是没看懂“最坏情况”——一文彻底吃透动态规划
为什么很多人刷不会《猜数字大小 II》？不是不会二分，而是没看懂“最坏情况”——一文彻底吃透动态规划
大家好，我是Echo_Wish。
很多人第一次刷到 LeetCode 的《猜数字大小 II（Guess Number Higher or Lower II）》时，第一反应往往是：
这不就是二分查找吗？
结果提交之后，Wrong Answer。
然后开始怀疑人生：
二分不是每次猜中间数字最快吗？
遗憾的是，这道题恰恰就是来"打脸二分"的。
它告诉我们一个非常重要的算法思想：
最快，不代表代价最小；平均最好，也不代表最坏最好。
这也是动态规划里非常经典的一类问题——极小化最大损失（Minimax DP）。
今天，我们就一起彻底搞懂这道经典面试题。
一、先理解题目到底在说什么
题目大概意思如下：
现在有一个数字。
范围：
1 ~ n