LeetCode 887 鸡蛋掉落

  • 分析
    比较经典的动态规划的题目,状态有两个一个是鸡蛋的数量,另一个是楼层的高度。选择就是在哪个楼层扔鸡蛋(可能在哪个楼层扔都可以求得f,选择一个在最坏情况下,扔次数最小的情况)。
  • 代码
class Solution {
public:
    int superEggDrop(int K, int N) {
        vector<vector<int>> middleResults(K + 1, vector(N + 1, 0));
        for (int i = 1; i <= N; i++) {
            middleResults[1][i] = i; // only one egg
            middleResults[0][i] = 0; // no egg
        }

        for (int k = 2; k <= K; k++) { // start from two egg
            for (int n = 1; n <= N; n++) {
                int tMinDrop = INT_MAX;
                for (int x = 1; x <= n; x++) {
                    tMinDrop = min(tMinDrop, 1 + max(middleResults[k - 1][x - 1], middleResults[k][n - x]));
                }
                middleResults[k][n] = tMinDrop;
            }
        }

        return middleResults[K][N];
    }
};


上一篇:Nmon Analyser工具的使用(4)


下一篇:Triumph Day9——C++ STL初识