麦克斯。产品动态规划

Question

因此，我试图解决麦克斯。产品问题，并提出了以下递归：

 maxProd(n) = max of [k*(n-k),k*maxProd(n-k),maxProd(k)*(n-k),maxProd(k)*maxProd(n-k)]

但是，在该链接上给出的第二个解决方案中，它们跳过了maxProd(K)*maxProd(N)。

int maxProd(int n)
{
    // Base cases
    if (n == 0 || n == 1) return 0;

    // Make a cut at different places and take the maximum of all
    int max_val = 0;
    for (int i = 1; i < n; i++)
      max_val = max(max_val, i*(n-i), maxProd(n-i)*i);

    // Return the maximum of all values
    return max_val;
}

这还对吗？如果是这样的话，是怎么做的？这不是给出了错误的答案当唯一的方法得到麦克斯。乘积是递归除以k和n-k？

Answer 1

你在这里写的公式也会起作用。但他们有一个更小的。

请注意，您可以从原始公式中得到任何解决方案，因为它检查了选择第一次剪切的所有可能方法。因此，如果第一个切割必须是我，那么我将被检查，并递归地继续到其他部分。

如果您使用回忆录，您将得到相同的运行时为这两个公式。