算法花园

tags:: #动态规划 #二分搜索
categories:: problem

• 题目连接：887. 鸡蛋掉落 - 力扣（LeetCode）

• 题解

  • 假设 dp[i][j] 代表 i 个鸡蛋移动 j 次最多能覆盖多少层楼，可以得到递推公式 dp[i][j]=dp[i-1][j-1] + dp[i][j-1] + 1，题目转换成求 dp[k][j]>=n 时最小的 j。这个递推公式增长速度很快，超过 n 后强制修改成 n 即刻。

• 代码

  • class Solution {
    public:
        int dp[101][10001];
        int superEggDrop(int k, int n) {
            memset(dp, 0, sizeof dp);
            for(int i=1;i<=k;i++) {
                for(int j=1;j<=n;j++) {
                    if(i==1) {
                        dp[i][j]=j;
                    } else {
                        if (dp[i-1][j-1]>=n || dp[i][j-1]>=n) {
                            dp[i][j] = n + 1;
                        }
                        else 
                            dp[i][j] = 1 + dp[i-1][j-1] + dp[i][j-1];
                    }
                    if(i==k&&dp[i][j]>=n) {
                        return j;
                    }
                }
            }
            return n;
        }
    };
    <!--code0-->