丢棋子问题最优解

这道题需要转换思路才能把时间复杂度降到O( ) 以下。基本思路是目前有i个棋子，如果扔j次最多能解决的楼层数。
构造二维dp，dp[i][j]表示i颗棋子，扔j次最多能解决的楼层数。

假设第1个棋子扔在a层楼是最优的尝试。
1.如果第1个棋子已碎，那就向下，看i-1个棋子扔j-1次最多搞定多少层楼。对应dp[i-1][j-1]
2.如果第1个棋子没碎，那就向上，看i-1个棋子扔j次最多搞定多少层楼。对应dp[i-1][j]
3.a层楼本身也是被搞定的1层。 +1
即有：dp[i][j] = dp[i-1][j-1] + dp[i-1][j] + 1

#include <vector>
#include <iostream>
#include <climits>
#include <algorithm>
using namespace std;

int log2Nplus1(int n) {//log2N + 1，其实就是求2进制位数
    int ans;
    while(n) {
        ans++;
        n >>= 1;
    }
    return ans;
}
int solutionONxK(int N, int K) {//参考左神的书的solution5，dp已经使用了滚动数组
    int ans = 0;
    int bestTimes = log2Nplus1(N);
    if(bestTimes <= K) {//棋子的数量多于二分查找的情形，直接返回二分筛选的次数
        return bestTimes;
    }
    vector<int> dp(K, 0); //dp[i]表示i+1个棋子仍j次能解决的最高楼层数，j++增长时dp[i]更新覆盖
    //这里是被迫使用滚动数组，因为j多大是未知的
    //dp[i][j] = dp[i-1][j-1] + dp[i-1][j] + 1
    //假设第1个棋子扔在a层楼是最优的尝试。
    //1.如果第1个棋子已碎，那就向下，看i-1个棋子扔j-1次最多搞定多少层楼。对应dp[i-1][j-1]
    //2.如果第1个棋子没碎，那就向上，看i个棋子扔j-1次最多搞定多少层楼。对应dp[i-1][j]
    //3.a层楼本身也是被搞定的1层。 +1
    while(true) {
        ans++;//扔的次数
        //参考https://www.nowcoder.com/questionTerminal/a74f0b4be3d140158ece1a77453384ac?f=discussion
        for(int i = K; i > 0; i--) {
            dp[i] = dp[i] + dp[i-1] + 1;
            if(dp[i] >= N) {//解决的楼层数达到预期
                return ans;
            }
        }
    }
    return ans;
}



int main() {
    int N, K;
    cin >> N >> K;
    cout << solutionONxK(N, K) <<endl;
    return 0;
}