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

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

您的代码断言(不包括边缘情况)

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}}

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