lc887. 鸡蛋掉落

题目连接：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;
    }
};

DFS 超时代码

class Solution {
public:
    int ans[101][10000+1];
    int dfs(int k, int n) {
        if (ans[k][n]!= -1) {
            return ans[k][n];
        }
        if (k == 1) return n;
        if (n == 1) return 1;
        int mi = n;
        for (int i = 1; i< n; i ++) {
            int f1 = dfs(k-1, i-1);
            int f2 = dfs(k, n-i);
            mi = min(1+max(f1, f2), mi);
        }
        ans[k][n] = mi;
        return mi;
    }
    int superEggDrop(int k, int n) {
        memset(ans, 0xff ,sizeof ans);
        return dfs(k,n);
    }
};