java - 在Java中使用递归进行动态编程(杆切割)

因此，我试图在Java工作中实现动态编程问题的简单实现。该方法是算法的切入点方法，第三版（Rivest等人撰写），第15章是我的代码-

public static double cutRod(double[] p, int n){
    if(n==0)return 0;
    double q = -1000;
    for(int i=0;i<n;i++){
        q = Math.max( q, p[i]+cutRod(p,n-i));
    }
    return q;
}

public static void main(String[] args) throws FileNotFoundException, IOException{
    double[] p = {1,5,8,9,10,17,17,20,24,30};
    double val = cutRod(p,10);
    System.out.println(val);
}

当我尝试运行此命令时，出现堆栈溢出错误。即使我尝试调试它（我使用的是netbeans），它在第一次递归调用时也会暂停一会儿，然后出现堆栈溢出错误。有任何想法吗？

最佳答案

令Road（n）为长度为n的杆的要求（最佳价格）值。 cutRod（n）可以编写如下。

cutRod(n) = max(price[i] + cutRod(n-i-1)) for all i in {0, 1 .. n-1}.

所以应该是n-i-1而不是n-i。

            q = Math.max( q, p[i]+cutRod(p,n-i-1));

请参考here