自顶向下棒料切割动态规划

Question

您如何使用自顶向下的方法来解决棒料切割问题，这样它将返回一个列表，列出从长度[0-棒长度]开始的所有棒的最大成本，并返回用于实现最大成本的零件？我成功地实施了自下而上的方法。在

def cutRod(pricelist):
    length = len(pricelist)
    r = [0] * length
    s = [0] * length

    for j in range(1, length):
        maxVal = 0
        for i in range(1, j + 1):
            if maxVal < pricelist[i] + r[j - i]:
                maxVal = pricelist[i] + r[j - i]
                if pricelist[j - i] != 0:
                    s[j] = [i, j - i]
                else:
                    s[j] = [i]
        r[j] = maxVal
    return r,s

但是，自上而下的方法是我所能做到的

^{pr2}$

到现在为止，这个函数只返回与列表大小相同长度的杆的最大成本。在

Answer 1

public static int cutRod(int arr[],int n,Integer memo[]){
    if(n<=0)
    return 0;
    int max=Integer.MIN_VALUE;
    if(memo[n]!=null)
    return memo[n];
    else{
        for(int i=0;i<n;i++)
        {
            max=Math.max(max,arr[i]+cutRod(arr,n-i-1,memo));
        }
        memo[n]=max;
        return memo[n];
    }
}

这是java中自顶向下的解决方案！在