题解 | #丢棋子问题# O(1)空间复杂度，数学优化
丢棋子问题
http://www.nowcoder.com/practice/d1418aaa147a4cb394c3c3efc4302266
———————————
听说搞OI的小孩
会把OEIS打印出来
然而我没有那么天才
所以数学优化整不明白
———————————
先上代码。
public int solve(int n, int k){
// 当棋子数大于logN+1时，直接返回logN+1
if(n < Math.pow(2, k - 1)){
// log2(n)可以用位运算求
return 31 - Integer.numberOfLeadingZeros(n) + 1;
}
// 从i = 1开始计算k个棋子扔i次能求解的最多楼层h
// h = C(i, 1) + C(i, 2) + ... + C(i, k)
// C为组合函数
for(int i = 1; ; i++){
int h = 0;
int c = 1;
int a = i;
for(int j = 1; j <= k && a > 0; j++, a--){
c = c * a / j;
h += c;
// 能求解的楼层高于n
if(h >= n){
return i;
}
}
}
}
对https://blog.nowcoder.net/n/d14c5eaaafe44f19bd0eca601d26049d?f=comment中最后一个解法中的表格进行观察（或者直接扔到OEIS里搜索）可以发现，对于一个确定的丢棋子次数m，以及一个确定的棋子数k，
k <= m时，最多能求解的楼层数h = C(m, 1) + C(m, 2) + ... + C(m, k)，C为组合函数（二项式系数）；
k >= m时，h = 2 ^ m - 1。
（k = m时，两式相等）
第一个式子并没有通项公式，不过对于给定的m我们可以以O(k)时间O(1)空间算出h。
因此我们要做的就是对于每个m从小到大依次算出相应的h，直到找到正好大于输入楼层数n的h。
总时间复杂度O(km)（同递归），空间复杂度O(1)。
当然可以用二分搜索优化，不过常数有点大，实际用时会超过O(km)的方法。
至于为什么h会满足第一个式子，先卖个关子，明日再叙。
————————————分割线————————————
这个题解居然有人看，那么展开说说。
为什么h = C(m, 1) + C(m, 2) + ... + C(m, k)？h为最多能求解的楼层数，丢棋子次数为m，棋子数量为k。
（如果不理解为什么要找最多能求解的楼层数，请参考其他题解的优化dp解法）
从k=2的情况考虑，显然，如果丢两个棋子丢m次，最后棋子要么都没碎，要么碎一个，要么两个都碎了。
举个例子，楼层高度h为5，从第3层开始扔。
第一个棋子没碎，在第4层继续扔，碎了说明最高第3层摔不碎，此时共摔碎一个棋子；
第一个棋子还没碎，则在第5层继续扔，碎了说明最高第4层，共摔碎一个棋子；没碎说明最高第5层，此时棋子都没碎（Good Ending!）
若在第3层棋子碎了，在第1层扔另一个棋子，碎了说明第0层摔不碎，此时棋子全碎；
另一个棋子在1层没碎，在第二层继续扔，同样有碎和不碎两个结果，两个结果分别确定两个不同楼层。
最多丢m次棋子，总共有C(m, 0) = 1种结果是棋子全不碎；
总共有C(m, 1) = m种结果是碎一个棋子，因为棋子可能在从第1次扔到第m次扔中的任意一次碎掉；
总共有C(m, 2)种结果是碎两个棋子，两个棋子都可能在从第1次扔到第m次扔中的任意一次碎掉，相当于从m个位置中选两个；
同理可得，总共有C(m, k)种结果是碎k个棋子。
而从之前的例子可以看出，扔m次棋子的每一种结果对应一个楼层，因此k个棋子扔m次共有C(m, 0) + C(m, 1) + C(m, 2) + ... + C(m, k)种情况，对应0到h的每个楼层。
因此h = C(m, 0) + C(m, 1) + C(m, 2) + ... + C(m, k) - 1 = C(m, 1) + C(m, 2) + ... + C(m, k)。
另外求解C(m, k)时有个小技巧，首先C(m, k)的形式如下：
很多人可能会直接用阶乘求，但是用java的话很容易溢出，所以最好用for循环迭代，每回乘一个分子上的数除一个分母上的数。
参考资料：
