algo-aha

K个鸡蛋N层楼、为确定安全楼层（最坏情况下）的最少步骤

• https://leetcode.com/problems/super-egg-drop/

设dp[k][i]表示k个鸡蛋i层楼（i>=1）、为确定安全楼层（最坏情况下）的最少步骤。当前鸡蛋在第i层扔，如果碎了，剩下k-1个鸡蛋在下面i-1层找，dp[k][i]=1+dp[k-1][i-1]；如果没碎，剩下k个鸡蛋在上面N-i层找（等价于在仅有N-i层的楼中找），dp[k][i]=1+dp[k][N-i]。所以，dp[k][i] = min( dp[k][i], max(1 + dp[k-1][i-1], 1 + dp[k][N-i]) )，max表示取最坏情况，min表示最少步骤。

因为dp[k][i]依赖于dp[k][N-i]，N-i可能>i也可能<i，i无论正序循环还是逆序循环都要依赖未知值，自底向上的dp无法计算。

只能带memo自顶向下递归计算。复杂度O(K*N^2)。运行超时。

优化递归里的O(i)循环，改成O(lgi)的二分搜索找i，复杂度O(K*N*lgN)。

上面方法还是太复杂，更好的方法是反过来想：

M个步骤K个鸡蛋、最多能确定多少层楼

int superEggDrop(int K, int N) {
	// 设dp[m][k]表示m个步骤k个鸡蛋、最坏情况下、最多检查的楼层数。
	// 假设在第i层扔鸡蛋（i>=1）：
	//  若鸡蛋碎，往下检查要覆盖下面的楼层，dp[m-1][k-1]>=i-1
	//  若鸡蛋不碎，往上检查要覆盖上面的楼层，dp[m-1][k]>=N-i
	// 两式相加，dp[m-1][k-1] + 1 + dp[m-1][k] >= N，覆盖了所有楼层
	// 所以，让 dp[m][k] = dp[m-1][k-1] + 1 + dp[m-1][k] 就能保证找到安全楼层
	// 初始dp[m][0]=0, dp[0][k]=0
	// 递推式在m维只依赖m-1项，可省掉m这维，m仍从左往右遍历
	// 要赋值右边的dp[k-1]表示旧状态，k从右往左遍历
	// dp[k] += dp[k-1] + 1
	vector<int> dp(K + 1, 0);
	int m;
	for (m = 0; dp[K] < N; m++) {
		for (int k = K; k >= 1; k--) {
			dp[k] += dp[k - 1] + 1;
		}
	}
	return m;
}

M=O(lgN)，所以复杂度O(K*lgN)。