一幢 200 层的大楼,给你两个鸡蛋。如果在第 n 层扔下鸡蛋,鸡蛋不碎,那么从第 n-1 层扔鸡蛋,都不碎。这两只鸡蛋一模一样,不碎的话可以扔无数次。最高从哪层楼扔下时鸡蛋不会碎?
递推关系大概是,当前需要扔一次所以加1。当前这一次可能是从1到n层的任意一层扔下,在n种情况中选择扔的次数最少的。当前这一次扔下,如果鸡蛋碎了,就只用试i-1层,鸡蛋剩下m-1个,如果鸡蛋没碎,就试剩下的n-i层,两种情况中取最大的,因为是最差情况。
至于100层时用14+13+12+……+1,大概是第一次选14层,如果鸡蛋碎了,就只能从第一层开始一层一层往上试,最坏情况下一共14次,如果没碎,第二次选14+13=27层,如果碎了,最坏情况下就从15层一直试到26层,一共也是14次,如果没碎,第三次再从27+12=39层试,以此类推……