自上而下切杆动态规划

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

但是使用自上而下的方法，这就是我所得到的

def cutRod(pricelist, cost, parts):
    length = len(pricelist)

    if length <= 0:
        return [0, cost, parts]

    maxVal = 0

    for i in range(0, length):
        w = pricelist[i]
        x, cost, parts = cutRod(pricelist[:length - i - 1], cost, parts)
        if maxVal < x + w:
            maxVal = x + w

    return [maxVal, cost, parts]

到目前为止，此函数仅返回与列表大小相同长度的杆的最大成本。

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中自顶向下的解决方案！