algorithm - 棒切割算法的替代方法(递归)

Question

在 Introduction To Algorithms 一书中，解决切杆问题的朴素方法可以通过以下重现来描述:

令 q 是可以从长度为 n 的杆获得的最高价格。

让数组 price[1..n] 存储给定的价格。 price[i] 是长度为 i 的杆的给定价格。

rodCut(int n)
{
    initialize q as q=INT_MIN

    for i=1 to n
        q=max(q,price[i]+rodCut(n-i))

    return q
}

如果我使用以下方法解决它会怎样:

rodCutv2(int n)
{
   if(n==0)
     return 0

    initialize q = price[n]

    for i = 1 to n/2
        q = max(q, rodCutv2(i) + rodCutv2(n-i))

    return q
}

这种方法是否正确？如果是，为什么我们通常使用第一个？为什么更好？

注意: 我只关心解决这个问题的方法。我知道这个问题展示了最优子结构和重叠子问题，可以使用动态规划有效地解决。

Answer 1

第二个版本的问题是它没有使用价格数组。递归没有基本情况，所以它永远不会停止。即使您添加条件以在 n == 1 时返回 price[i]，它也始终会返回将杆切割成尺寸为 1 的碎片的结果。