shellbye

same issue

可以说是非常的赞了

Did this fixed?

@dww102 嗯，O(KN）应该是最差情况了

@BlueRhino 这个图不是我画的，是第二个参考文献里面的图，不过我觉得这个图可能不是用特殊软件画的，而是可能用的手写板

> @Shellbye > 还有一种写法,空间复杂度只有`O(K)`,时间复杂度`O(KlogN)` > > ``` > vector dp(K + 1, 0); > int m; > for (m = 0; dp[K] < N; m++) > for (int k =...

> 只是把dp矩阵中二维元素换成了次数s > > ``` > dp[k][s] = d[k][s-1] + dp[k-1][s-1] + 1; > ``` > 简化掉s用一维数组保存对应的数据,就是 > > ``` > dp[k] = dp[k] + dp[k-1] + 1; > ```...

> 最后一种做法： > 1.鸡蛋碎了，测出N - X + dp[k-1][m-1]层 > 2.没碎，测出X + dp[k][m-1]层 > 为什么状态转移方程是：dp[k][m] = dp[k][m - 1] + dp[k - 1][m - 1] + 1 > 可以再详细解释一下相加的含义以及+1的含义吗？ 这个相加，并不是说是两种情况加起来的意思，而是`未来可能测出来的数量 +...

@DaDaDoDoLee > 既然结果是不确定的，那么为什么不是得到当前最多能测出的层数呢？也就是说状态方程为什么不是： dp[k][m] = max(dp[k][m - 1] , dp[k - 1][m - 1]) + 1 ? 我在原文中加了点说明，这里不是两种情况的比较，而是其中一种情况的计算

@njulzb > 应该这么理解，F(t,k) 要求一定要测出 N层，思考如果要达到这个目标，丢下的第X层如何选择，就是要保证如果鸡蛋碎了，比X低的层数一定要能够用F(t-1,k-1)确定出来，如果鸡蛋没碎，比X高的层数一定要能够用F(t-1,k)确定出来，再加上本层，就是能够确定的最大层数 反过来理解的话是这样的