我在解决与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的正确算法。
最佳答案
您的代码断言(不包括边缘情况)
eggDroppingPuzzle(eggs, floor) = 1+eggDroppingPuzzle(n-1,k/2-1)
这意味着:
你假设每一滴鸡蛋都会破(因为剩下的n-1个鸡蛋),而且
你的策略是总是从剩余楼层的中间往下掉(因为k/2-1剩余楼层)
这两个假设通常都是错误的,因为其目的是最小化滴数。例如,你的策略,
EggDroppingPizzle(2100)=1+EggDroppingPizzle(149)
因为EggDroppingPizzle(1,49)=49,这意味着,对你来说EggDroppingPizzle(2,100)=50,远远大于正确答案14。这是因为你的策略不是最优的,因为这些错误的假设。
递归策略没有这样的假设。它简单地说明了显而易见的:
蛋液(n,k)=1+min{max(蛋液(n-1,x-1),蛋液(n,k-x)):
其中x在{1,2,…,k}
显然,动态编程只是递归逻辑的自下而上的方法,在这种方法中,您将时间(重复计算)换成空间(存储数组)。
是的,dp方法是一种优化的暴力方式。没有什么聪明的策略只是探索所有的状态直到解的状态。
关于algorithm - 使用动态编程方法进行丢蛋难题有什么需要?,我们在Stack Overflow上找到一个类似的问题:https://stackoverflow.com/questions/32936735/