丢棋子问题

这题关键是在变换思路，将原问题中的最少需要几次变换成，拥有i个棋子，扔j次最多可以测试出多少楼高，所以状态转移方程可以写成：

dp[i][j] = d[i][j-1] + dp[i-1][j-1] + 1

n, k = map(int, input().split())
l = [i for i in range(n+1)]
if k == 1:
    print(n)
else:
    sign = False
    floor = 2
    while True:
        tmp = [1] * n
        for i in range(2,n+1):
            tmp[i] = l[i-1] + tmp[i-1] + 1
            if floor != k and tmp[i] >= n:
                break
            if floor == k and tmp[i] >= n:
                sign = True
                print(i)
                break
        if sign:
            break
        floor += 1
        l = tmp

Python解法超时了，但是一样的解法用C就不超时 emmmmm

#include <bits/stdc++.h>
using namespace std;

int main(){
    int n,k,cnt=0;
    cin>>n>>k;
    int dp[k+1];
    memset(dp, 0, sizeof(dp));
    while(true){
        cnt++;
        for(int i=k;i>0;i--){
            dp[i] = dp[i] + dp[i-1] + 1;
            if(dp[i]>=n){
                cout<<cnt<<endl;
                return 0;
            }
        }
    }
    return 0;
}