题解 | #丢棋子问题#动态规划的两种思维

	/**
     *O(n*k)的解法，这种解法就是通常想到的正向思维，由于不知道在哪一楼丢下就会碎，
     *所以需要从i楼开始进行尝试
     *如果i楼碎了，那么就得以左边为子过程去查最少需要多少次能得出答案了。
     *如果i楼没碎，那么就得以右边为子过程去查最少需要多少次能得出答案了。
     *
     *由于每次都是最坏情况，所以这两个子过程得考虑次数多的那个，而之所以遍历1~n开始丢棋子
     *选出最少的那个是因为我们要求的就是最少的次数，所以需要尝试所有丢下去的情况，
     *找出最少的那个
     *
     *这里可变参数是n和k，所以这个改写之后外层最少都得是O(n*k)的时间复杂度，内层还嵌套
     *着一个1~n的循环，这个循环还不太好压缩去掉，顶多利用单调性改成logN的查找，那还是
     *无法满足题意。
     */
	public int process(int n,int k){
        if(n==0) return 0;
        if(k==1) return n;
        //1.从第1~n-1层楼尝试丢下去，不管碎和不碎都能解决一个层的问题
        int min = Integer.MAX_VALUE;
        for(int i = 1;i<n;i++){
            //2.尝试从i楼丢下，碎了向左，没碎向右
            min = Math.min(min,1+Math.max(process(i-1,k-1),process(n-i,k)));
        }
        return min;
    }
	/**
     *正向思维完成不了的事情通常逆向思维就能完成，这也是动态规划中的一种套路，
     *假设现在有一个函数，y=f(x),现在要求当y=7的时候x是多少？
     *正向思维就是我去模拟流程，小样本量得到一个小的解(比如f(1)=3,f(2)=4...)
     *，然后解去和要求的解逼近。
     *
     *而逆向思维则是用从小的解开始，不断算出一个x的值看到满足y=7的时候的x是啥，那就是答案。
     *
     *以这道题来说呢，正向思维就是，f(n,k)最少的次数是多少？
     *               逆向思维就是，f(t,k),也就是抛t次，最多能判断多少层？
     */
    public int solve (int n, int k) {
        //dp[row][col] 表示row个棋子和col次丢的机会能够找到棋子不会摔碎的最高层数
        int t = 1;
        for(int col = 1;;col++){
            for(int row = 1;row<=k;row++){
                if(process2(t,row)>=n){
                    return t;
                }
                t++;
            }
        }
    }
    //t次机会，k个棋子最多能判断多少层楼
    public int process2(int t,int k){
        if(t==1) return 1;
        if(k==1) return t;
        //两种可能，当前这颗棋子丢出去碎了还是没碎，可以分别看两边，从而最终能判断的高度是两边加起来的高度
        return 1+process2(t-1,k)+process2(t-1,k-1);
    }
    public int solve (int n, int k) {
        //每次只依赖左边一条位置，所以使用两个一维数组做压缩矩阵
        int[] lastArr = new int[k+1];
        int[] curArr = new int[k+1];
        int t = 1;
        for(int col = 1;;col++){
            for(int row = 1;row<=k;row++){
                //1.填curArr
                if(col==1) 
                    curArr[row] = 1;
                else if(row==1) 
                    curArr[row] = col;
                else{
                    curArr[row] = 1 + lastArr[row-1] + lastArr[row];
                }
                if(curArr[row]>=n) return t;
            }
            //2.两个arr交换
            int[] temp = lastArr;
            lastArr = curArr;
            curArr = temp;
            t++;
        }
    }