之前被某小哥以智商测试题一般的考过一道题：
100层楼，球可能会在某一层楼摔碎，问用2个球，最坏情况下几次测试可以找出该楼层？
以哥们这种博闻强识的脑子，当时就给出了答案：14。
某小哥不以为意，微微一笑：“怎么算出来的？”
思考半天未果，只好老老实实的交代：”之前从百度上看到的，好像是个谷歌的面试题，我回去好好学习学习再出来跟你装逼……“
于是便引出了这篇关于动态规划的思考。
先上俩动态规划的百科链接，以供大家观赏(根据自己的逼格自行挑选)：
我再稍微跟大家唠一唠啥叫动态规划，说白了就是——如何把一件听上去就很烦人的事，分解成一件件不是那么烦人的事。
这么一说，是不是突然就有种茅塞顿开的感觉？！卧槽？好像什么都能适用啊？然而并不是……想搞动态规划，还需要满足下面2个条件才行。
1.具有最优子结构。即无论过去未来如何变化，将最优子结构得出的解，永远都是每一个子结构里的最优解。
2.无后效性。这个名字听上去可能有点儿懵，那咱们看看它的定义：每个状态都是过去历史的一个完整总结。惊不惊喜？是不是更懵了？emmmm……我一开始也挺懵，简单点儿说，就是”一个事情，可以被划分阶段，划分阶段后，未来的事情，不再受之前状态的影响“，举个反例吧：玩游戏棋的时候，突然加了个规矩，不能走重复的格子，这也就意味着，你每一步的动作，都会影响到未来的动作。整件事情，是无法被划分阶段的。因为当你走过了这一步，未来就不能走这一步了。未来永远会受到影响。
大概清楚了么？动态规划的两个要求，下面还是回归到这道题上来。
先捋一捋思路。咱先忘了刚才说的这些逻辑概念啥的，从一个小懵逼开始捋思路。
2个球，测临界点。咋测？
先说最笨的方法吧——一层一层的来。反正我从底测到顶，哪层摔碎了哪层就是临界值。
这也就是大家最喜欢的方法，暴力穷举（我知道，我又懂你了）
暴力穷举是人类进步的阶梯——鲁迅
当然，如果只有一个球，咱们也只有这一种办法，因为，摔碎了就没球了。
所以说，这道题妙就妙在这里了，他给了两个球！
两个球！题目作者想向我们表达什么呢？
每个男人都应该有两个球！少一个都是不健全！
这是在给我们试错的机会啊！有了试错，是不是问题一下就好解决多了？
50楼一扔，碎了往下面找，没碎往上面找。
这是啥？同学们！二分法啊！
是不是一下子就觉得，蹭蹭蹭蹭蹭，速度瞬间就上来了！50楼没碎，75楼接着摔，再没碎87楼……反之50楼碎了，25楼接着摔，要是25楼再碎了……再碎了……再碎了好像就没球了……
没球了岂不是完蛋了！所以如果50楼碎了，下一个球，就只能从1楼开始扔，一直扔到50层。二分法这时也陷入了瓶颈。最坏的情况下，需要测50次。
那还有没有更简单的办法呢？
啥？不知道？我开头絮叨了那么一堆，你跟我说你不知道？！
认真读题同样是人类进步的阶梯——鲁迅
是的，动态规划，老带劲了！
要用动态规划，咱们就先套一套，这个东西能不能用动态规划来做。
首先第一点，无后效性，要知道一个有后效性的事件是无法用动态规划去解决的，那么看看这个事件，是否符合呢？我们一步步来，先分阶段，我们可以把每一次扔球分成一个阶段，而每一次扔球的结果，都是对当前阶段的一个总结，即——每次结果，都会告诉我，当前楼层会不会把球摔碎。当你下次再扔球的时候，无论高低或在同楼层扔，都不会受到本次结果的影响，那么我们可以断定，这个事件，是一个无后效性的事件。
其次，具有最优子结构。首先从上面无后效性的判断我们发现，该事件具有子结构是毋庸置疑的，每次扔球，都是一个子结构事件，那么接下来，我们只需要去思考，如何找到最优的子结构事件就好了。
如何判断最优呢？这时候就要从我们的需求入手了。我们需要找到最坏情况下最少需要的步数。也就是说，咱们根本不用考虑最快的时候能有多快，只要保证无论这个楼层出现在哪，这个结果都还可以，也就是，我们算法的稳定性需要保证。听上去有点儿绕，不用着急，咱们可以先从结果反推。
我们可以先思考这样的一个问题，我们有两个球，明明一个球暴力穷举就可以解决了，那么另一个球的作用是干什么的呢？这时大家脑子里肯定瞬间就萌生出一个想法，锁定范围。没错，如同之前二分法的逻辑，第一个球扔在了50楼，那么他无论破碎与否，都帮我们排除掉了50层的问题，这就顺利的把球从100层锁定在了50层以内。然而球会碎的逻辑，阻碍了二分法的继续进行。而球会碎这个初始条件，也使我们发现，无论何时，第一个球碎掉之后，第二个球都需要从区间的最底部开始一层一层的测试，直到试到上一个球碎掉所在楼层-1的楼层。
这时候问题就开始有眉目了。在1球没碎的楼层到1球碎掉的楼层之间，用2球一层一层的测试，直到测试出临界楼层——这其实就是我们的最优子结构——在1球确定的范围内，用2球逐层检查。所以我们可以先从最初开始算起，假设1球上来就碎掉了：
总次数 = 2球测试的层数 = （1球选择的层数） - 1
而反之，如果1球第一次没有碎掉呢？那么这个算式就变成了：
总次数 = 2球测试的层数 +1
2球测试的层数 = （1球选择的第二次层数） - （1球选择的第一次层数）
再向上同理：
总次数 = （1球选择的第n次层数） - （1球选择的第n-1次层数）+ n-1
我们肯定是希望，每次的总次数，都是相等的，这样才能保证我们代码的一个稳定性。因此，每向上一层，我们的1球选择的层数区间，都一定会比上一次选择的区间少1，以保证稳定性。
嗯……亚克西，到这里，我们已经找到了一个合适的思路了。那么下面，就是看如何算出这个数来了。
假设n为第一次选择的层数，那其实就可以换算成这个样子了：
n+(n-1)+(n-2)+…+2+1 >=100
是的，连代码都不用敲了。
n+(n-1)+(n-2)+…+2+1 >=100
1+2+…+(n-2)+(n-1)+n>=100
两式合并
(n+1)n>=200，一元二次方程了解一下？
最后结果，n最小等于14（可算得出这个数了！）。
由一个完全没有头绪的破玩意儿，让我们通过动态规划的思路，最终弄成了一个一元二次方程。
老铁们，有没有感受到动态规划的魅力所在？！
