什么是需要使用动态规划方法来解决掉蛋难题？

Question

我在解决DP相关问题，遇到了泛化egg dropping puzzle。我可以使用不重复子问题的分而治之来解决这个问题。所以我相信不需要DP来解决掉蛋难题。谁能告诉我以下算法是否适用于不需要 DP

的地方

n- eggs
k-floors
initial call : eggDroppingPuzzle(n,k)
eggDroppingPuzzle(eggs, floor)
{
 if floor==1 return 1;
 else if eggs=1 return K;
 return 1+eggDroppingPuzzle(n-1,k/2-1);// problem is reduced by (size/2)-1
}

由于每次递归调用都没有重叠的子问题，所以我觉得不需要动态规划

谁能解释一下我的不需要 DP 的算法是否正确。如果不正确，请向我解释使用 DP 的正确算法。

Answer 1

可能存在最佳落蛋的封闭形式，但事实并非如此。有两个鸡蛋，您将第一个从半途掉落，如果它破裂，您将感到非常抱歉，因为您必须使第二个掉落 k/2。一个更好的（但不是最优的！）两个鸡蛋的策略是第一个鸡蛋一次上升 √k 层，最多 k/√k = √k 次掉落，最多 √k 次掉落第二。一般来说，动态程序最佳地平衡了拆分搜索的价值 space 与打破鸡蛋的成本。

Answer 2

您的代码断言（不包括边缘情况）

eggDroppingPuzzle(eggs, floor) = 1+eggDroppingPuzzle(n-1,k/2-1)

这意味着：

你假设每一滴鸡蛋都会破裂（因为剩下 n-1 个鸡蛋），并且
你的策略是始终从剩余楼层的中间掉落（因为 k/2 -1 剩余楼层）

这两个假设通常都是错误的，因为目的是尽量减少掉落的数量。例如，根据您的策略，

eggDroppingPuzzle(2, 100) = 1 + eggDroppingPuzzle(1, 49)

并且因为 eggDroppingPuzzle(1, 49) = 49，这意味着，对你来说 eggDroppingPuzzle(2, 100) = 50，这远远大于正确答案 14。这是因为你的策略不是最优的，因为这些错误的假设。

递归策略不做这样的假设。它简单地说明了显而易见的事实： eggDrop(n, k) = 1 + min{max(eggDrop(n - 1, x - 1), eggDrop(n, k - x)): 其中 x 在 {1, 2, ..., k}}

显然，动态规划只是递归逻辑的自下而上方法，您用时间（重复计算）换取 space（存储数组）。是的，DP 方法是一种优化的蛮力方法。没有涉及聪明的策略。探索所有状态直到解决方案状态。

什么是需要使用动态规划方法来解决掉蛋难题？

what is the need to use Dynamic programming approach for egg dropping puzzle?

puzzle

algorithm

dynamic-programming