[数据结构与算法]0动态规划中等 NC87 丢棋子问题

NC87 丢棋子问题

描述

一座大楼有层，地面算作第0层，最高的一层为第 层。已知棋子从第0层掉落肯定不会摔碎，从第层掉落可能会摔碎，也可能不会摔碎。
给定整数作为楼层数，再给定整数作为棋子数，返回如果想找到棋子不会摔碎的最高层数，即使在最差的情况下扔的最小次数。一次只能扔一个棋子。

用k个棋子(鸡蛋)丢m次，最多能确定多少层

当确定的楼层个数超过n，则返回此时的m。
dp[k][m]表示k个棋子(鸡蛋)，丢m次，最多能确定的多少层数。
动态转移方程：
dp[k][m]仍然由破裂的鸡蛋和未破裂两种情况构成，即
dp[k][m] = dp[k1][m-1] + dp[k1-1][m-1] + 1;

import java.util.*;
public class Solution {
    public int solve (int n, int k) {
        int[][] dp = new int[k+1][n+1];
        if(n == 0 || k == 0){
            return 0;
        }
        int m = 0;
        //当dp[k][m] >= n时，跳出循环，返回m，即最少需要扔m次
        for(; m <= n && dp[k][m] < n; ){
            m++;
            for(int k1 = 1; k1 <= k; k1++){//因为求dp[k1][m]依赖dp[k1-1][m-1]，所以从上向下遍历
                if(k1 == 1){
                    dp[k1][m] = m;
                    continue;
                }
                if(m == 1){
                    dp[k1][m] = 1;
                    continue;
                }
                dp[k1][m] = dp[k1][m-1] + dp[k1-1][m-1] + 1;
            }
        }
        return m;
    }
}

直观的动态规划

缺点是时间复杂度大
dp[i][j] 表示i层楼，j鸡蛋(棋子)最少需要扔多少次才能确定临界的楼层
动态转移方程：
dp[i][j] = Math.min(dp[i][j],Math.max(dp[i-t][j],dp[t-1][j-1])+1)
dp[i][j] 由破裂的鸡蛋和未破裂两种情况构成,取其中最大值，遍历所有第一次扔鸡蛋的位置，取最小的dp[i][j] 。

import java.util.*;
public class Solution {
    public int solve (int n, int k) {
        int[][] dp = new int[n+1][k+1];
        if(n == 0 || k == 0){
            return 0;
        }
        for(int i = 1; i <= n; i++){
            for(int j = 1; j <= k; j++){
                if(j == 1){
                    dp[i][j] = i;
                    continue;
                }
                dp[i][j] = Integer.MAX_VALUE;
                for(int t = 1; t < i+1; t++){
                    dp[i][j] = Math.min(dp[i][j],Math.max(dp[i-t][j],dp[t-1][j-1])+1);
                }
            }
        }
        return dp[n][k];
    }
}