Динамическое программирование - Алгоритм реза снизу вверх (CLRS) Решение Неверно?

Question

Для задачи «резка стержня»:

Учитывая стержень длиной n дюймов и массив цен, который содержит цены на все кусочки размером меньше n. Определите максимальное значение, которое можно получить, разрезая прут и продавая кусочки. [ ссылка ]

Введение в алгоритмы (CLRS) на стр. 366 приведен этот псевдокод для восходящего (динамического программирования) подхода:

1. BOTTOM-UP-CUT-ROD(p, n)              
2. let r[0 to n]be a new array .        
3. r[0] = 0                             
4. for j = 1 to n                       
5.     q = -infinity                    
6.     for i = 1 to j                   
7.         q = max(q, p[i] + r[j - i])  
8.     r[j] = q                         
9. return r[n]                          

Теперь у меня проблемы с пониманием логики, стоящей за строкой 6. Почему они делают max(q, p[i] + r[j - i]) вместо max(q, r[i] + r[j - i])? Поскольку это подход снизу вверх, сначала мы вычислим r[1], а затем r[2], r[3].... Это означает, что при вычислении r [x] у нас гарантированно будет r [x - 1].

r [x] обозначает максимальное значение, которое мы можем получить для стержня длины x (после обрезки до максимизации прибыли), тогда как p [x] обозначает цену одного куска стержня длины x. Строки 3-8 вычисляют значение r[j] для j = 1 до n, а строки 5-6 вычисляют максимальную цену, за которую мы можем продать стержень длины j, рассматривая все возможные сокращения. Итак, как же имеет смысл использовать p [i] вместо r [i] в ​​строке 6. Если мы пытаемся найти максимальную цену за стержень после того, как мы разрезаем его на длину = i, не следует ли нам добавить цены из r [i] и r [j - 1]?

Я использовал эту логику для написания кода Java, и, похоже, он дает правильный вывод для ряда тестовых случаев, которые я пробовал. Я пропускаю некоторые случаи, когда мой код приводит к неправильным / неэффективным решениям? Пожалуйста, помогите мне. Спасибо!

class Solution {
    private static int cost(int[] prices, int n) {
        if (n == 0) {
            return 0;
        }

        int[] maxPrice = new int[n];

        for (int i = 0; i < n; i++) {
            maxPrice[i] = -1;
        }

        for (int i = 1; i <= n; i++) {
            int q = Integer.MIN_VALUE;

            if (i <= prices.length) {
                q = prices[i - 1];
            }

            for (int j = i - 1; j >= (n / 2); j--) {
                q = Math.max(q, maxPrice[j - 1] + maxPrice[i - j - 1]);
            }

            maxPrice[i - 1] = q;
        }

        return maxPrice[n - 1];
    }


    public static void main(String[] args) {
       int[] prices = {1, 5, 8, 9, 10, 17, 17, 20};

        System.out.println(cost(prices, 8));
    }
}

Answer 1

Я думаю, что оба подхода верны.

прежде чем мы докажем, что оба они верны, давайте определим, что именно делает каждый подход

p [i] + r [j - i] даст вам максимальное значение, которое вы можете получить из стержня длины j, а кусок имеет размер "i" (не может разделить этот кусок дальше)

r [i] + r [j-i] даст вам максимальное значение, которое вы можете получить от стержня длины i, а первый разрез был сделан на длине "i" (можно разделить обе части дальше)

Теперь рассмотрим, что у нас есть стержень длины X, и набор решений будет содержать кусок длины k

и поскольку k равно 0

и во втором подходе вы можете найти тот же результат с помощью r [k] + r [X-k], поскольку мы знаем, что r [k] будет> = p [k]

Но при подходе вы можете получить результат намного быстрее (в половине случаев), так как вы нарезаете удочку с обоих концов поэтому при подходе вы можете запустить внутренний цикл, так как половина длины должна быть хорошей.

Но я думаю, что в вашем коде есть ошибка во внутреннем цикле for это должно быть j> = (i / 2) вместо j> = (n / 2)

Answer 2

Они должны быть эквивалентны.

Интуиция, лежащая в основе подхода CLRS, состоит в том, что они пытаются найти единственный «последний разрез», предполагая, что последний кусок стержня имеет длину i и, таким образом, имеет значение точно p[i]. В этой формулировке «последний кусок» длины i не обрезается дальше, но остаток длины j-i равен.

Ваш подход учитывает все расщепления стержня на две части, где каждая из двух частей может быть разрезана дальше. Это учитывает множество случаев по сравнению с подходом CLRS.

Оба подхода верны и имеют одинаковую асимптотическую сложность. Тем не менее, я бы сказал, что решение CLRS является более «каноническим», поскольку оно более точно соответствует распространенной форме решения DP, где вы рассматриваете только последнюю «вещь» (в данном случае, последний кусок неразрезанного стержня).