前些天很多研三的师兄在刷线上的笔试题，看到腾讯的一道简答题，挺有意思的。
当时没想明白，事后查了一下网上的资料，自己又重新思考了一下。这道题之前似乎被很多公司用过。
这道题网上有很多的解析，但是几乎都是复制来复制去，完全相同的方法思路。不得不说这是一种互联网信息的病态。
原题描述如下：
某幢大楼有100层。你手里有两颗一模一样的玻璃珠。当你拿着玻璃珠在某一层往下扔的时候，一定会有两个结果，玻璃珠碎了或者没碎。这幢大楼有个临界楼层。低于它的楼层，往下扔玻璃珠，玻璃珠不会碎，等于或高于它的楼层，扔下玻璃珠，玻璃珠一定会碎。玻璃珠碎了就不能再扔。现在让你设计一种方式，使得在该方式下，最坏的情况扔的次数比其他任何方式最坏的次数都少。也就是设计一种最有效的方式。
（腾讯的简答题中照搬了原题，只改了下楼层数）
自己的读完题的第一感觉：
应该很多人和我一样，第一反应是二分法，基于两点：
1.楼层号是有序的，有序是二分法有效的前提
2.要找到一个确定的楼层号
但是仔细读题，重要的题目条件是玻璃球只有2个，碎了就没了，二分查找卒。
可以肯定的结论是：一旦第一个球碎了，那之后就只能从已知安全的最低楼层一直到第一个球碎了的楼层，从下 往上逐一尝试，直到找到为止。
如果按照二分，第一次在50楼，如果球碎了，那就得从1楼开始，最坏情况需要1+49次，感觉这明显不是正确答案。
其实思路还是被二分约束住了，想来想去也没有好的思路。
事后看了网上的答案分析，千遍一律的使用DP的思想。
这个想法大致可以描述如下（具体思路可以看底部给的链接）：
选定一个楼层n，从n丢下去有2种情况：
1.球碎了，那就从最下面到n-1层依次尝试，最坏情况为n
2.球没碎，那问题就转化为100-n楼的情况（已确定n以下的楼层都是安全的，想象砍掉n下方的楼层，目前只剩100-n层了），动态规划中即可以利用之前已有的解，最坏情况F[100-n]+1
那么对于每一个n的选择，其最坏情况就是1和2中的较大者。
对于100层来说，第一次n的选取可以是1-99。
网上给出的代码要么是递归的，要么是二层循环的。
讲真，第一次看到这个DP解法感觉很巧妙的样子，细想其实不然，对于第一个想到这个办法的人应该是聪明的，但是后续不断传承这个方法的人那就是愚钝的了。
我们重新来理一下思路，重点放在每次的n应该如何选取上：
第一次选楼层n1丢下去，
1.如果球碎了，那就从1层开始往上，最坏情况就是n1
2.如果球没碎，那就选一个楼层n2（n2的选择是这里的关键）
（1）如果选择的n2大于等于n1，
1.如果碎了，那最坏情况就得尝试n2+1次，当前的最坏情况已经超过了上一步的最坏情况了，没有继续分析下去的必要了
（2）那如果选择的n2小于n1呢？
1.球碎了，最坏情况是n2+1（此时n2+1是小于等于n1的，说明n2小于n1的选择是有意义的）
2.球没碎，那么依然是砍掉n2及以下的楼层来简化问题，继续选择n3
n3的选择过程同n2。
可以看到两点
1.按照这个思路n1,n2,n3…必须是一个递减的序列，如果玻璃球一直没碎，那就直到n1+n2+n3+…的和超过楼层数为止
2.由于n的选择序列递减的性质决定了每次n的选择不能太小。比如n1=20，n2=2,那n3就只能选择1了，这明显是不明智的
其实分析到这，应该大致有数了，选择n2=n1-1是最佳的做法，那么继续选择n3=n2-1，依次。
也就是整个n序列是个差值为1的等差递减序列。
等差序列求和超过最大楼层数即可，根本用不着DP，直接设n1为x,求（x, x-1,x-2,…,2,1）的和大于等于100，解出最小的x，就是最终的答案。
来自网上的解法
PS：网上的答案都是复制来复制去，这篇也不一定是原文，对原文作者表示歉意。