Динамическое программирование Top Down Rod Cut

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!