美文网首页
584.Drop Eggs II

584.Drop Eggs II

作者: 博瑜 | 来源:发表于2017-07-23 21:29 被阅读0次

There is a building of n floors. If an egg drops from the k th floor or above, it will break. If it's dropped from any floor below, it will not break.

You're given m eggs, Find k while minimize the number of drops for the worst case. Return the number of drops in the worst case.

Example
Given m = 2, n = 100 return 14
Given m = 2, n = 36 return 8

public class Solution {
/**
 * @param m the number of eggs
 * @param n the umber of floors
 * @return the number of drops in the worst case
 */
    int dropEggs2(int m, int n) {
    // Write your code here
    int[][] state = new int[n + 1][m + 1];
    for (int i = 1; i < m + 1; i++) {
        state[1][i] = 1;
    }
    for (int i = 1; i < n + 1; i++) {
        state[i][1] = i;
    }
    for (int i = 2; i < n + 1; i++) {//n ---> floor
        for (int j = 2; j < m + 1; j++) {//m ---> eggs
            int min = Integer.MAX_VALUE;
            for (int k = 1; k < i + 1; k++) {
               min = Math.min(Math.max(state[k - 1][j - 1], state[i - k][j]),min);
            }
            state[i][j] = min + 1;
        }
    }
    return state[n][m];
}
//f[t][p] = min(max(f[s - 1][p - 1]),f[t - s][p])|s=1...t) + 1
//总共t层,在s层扔p个蛋
}

相关文章

  • 584.Drop Eggs II

    There is a building of n floors. If an egg drops from the...

  • Dragons’ Eggs II

    本周继续阅读了上周没有阅读完的英文小说,终于在今天完成了阅读,这个故事还是很有意思的。 接着上周的情节发展,这一次...

  • How do I make tomato and egg noo

    First, buy some eggs and brake three eggs into the bowl. ...

  • How to make tomato and egg noodl

    First,Scatter eggs Nest,Stir fry tomatoes and eggs in a p...

  • egg的复数怎么读

    egg的复数形式是eggs。音标:[eɡz]。短语:a dozen eggs,一打鸡蛋。例句:Eggs are g...

  • 2018-02-23

    def spam():"""Prints 'Eggs!'"""print "Eggs!"spam() 注意别漏了这...

  • 2018-02-17

    def spam():eggs = 12return eggs print spam() codecademy 1...

  • Eggs Dropping puzzle(2 eggs, 100

    题目如下: You are given two eggs, and access to a 100-storey ...

  • hen eggs

    SUPPORT: huanglittledragon@gmail.com Protect the egg from...

  • Dragons’ Eggs

    本周继续阅读这一系列中的另外一本英文小说。 这本书的内容似乎就与我们有一些的遥远了。故事发生在非洲,一个普普通通的...

网友评论

      本文标题:584.Drop Eggs II

      本文链接:https://www.haomeiwen.com/subject/gozmkxtx.html