题解 | #丢棋子问题#

import java.util.*;

public class Solution { /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * 返回最差情况下扔棋子的最小次数 * @param n int整型 楼层数 * @param k int整型 棋子数 * @return int整型 */ public int solve (int n, int k) { // write code here if(n<1 || k < 1) return 0; if(k==1) return n; int bsTime = (int)(Math.log((double)n)/Math.log((double)2)+1); if(k >= bsTime) return bsTime; int[]dp = new int[k]; int res = 0; while(true){ ++res; int previous = 0; for(int i = 0; i < dp.length; i++){ int tmp = dp[i]; dp[i] = dp[i] + previous + 1; previous = tmp; if(dp[i] >= n) return res; } } // int t=0; // int max=0; // while(max<n){ //最多能确定的楼层大于等于n时返回找到的次数 // ++t; // for(int i=1;i<=k;i++){ //在不超过的k个棋子中选择 // max = dp(t,i); //t次i个其中能确定的最大楼层数 // } // } // return t; }

public static int dp(int t,int k){
    /*扔t次，k个棋子最多能确定的楼层数**/
    if(t==1){return 1;}
    if(k==1){return t;}
    //dp(t-1,k)对应没碎，dp(t-1,k-1)对应碎了，
    //1为当前楼层丢的一次确定了当前层
    return 1+dp(t-1,k)+dp(t-1,k-1);
}

}