Проблема с обрезкой стержня: альтернативное повторение в интервью

Как уже отмечалось, оба рекуррентных отношения имеют проблемы:

1. x[n] = max(p[i] + x[n-i]); 0 <= i <= n

   Здесь i может быть 0, что будет определять x[n] в терминах самого себя (бесконечная рекурсия). Не уточняется, предусмотрен ли p[0]. Если он предусмотрен, он обязательно должен быть равен 0, чтобы иметь смысл.

   Кроме того, i может быть n, что приведет к запросу x[0], но тогда нам нужно определить x[0] как отдельный базовый случай, поскольку мы уже исключили, что i может быть 0 в предыдущем пункте. Конечно, тогда x[0] следует определить как 0.

   x[0] = 0
x[n] = max(p[i] + x[n-i]); n > 0, 0 < i <= n

   Поскольку x[n] = p[n] сейчас рассматривается как кандидат, и это также базовый случай (n == 0), мы могли бы встроить этот параметр в операцию max и рассматривать i < n только для других кандидатов:

   x[n] = max(p[n], p[i] + x[n-i] for 0 < i < n)

   
   

2. x[n] = max(x[i] + x[n-i]); 1 <= i <= n-1

   Этот предотвращает граничные проблемы для i, но не рассматривает случай, когда стержень размера n не следует обрезать, и в этом случае x[n] = p[n].

   Поскольку условия суммы взаимозаменяемы, мы можем ограничить i до n/2, но тогда все равно придется учитывать x[n] = p[n].

   x[n] = max(p[n], x[i] + x[n-i] for 0 < i <= n / 2)

В итоге у нас есть две альтернативы:

1. x[n] = max(p[n], p[i] + x[n-i] for 0 < i < n)
2. x[n] = max(p[n], x[i] + x[n-i] for 0 < i <= n / 2)

Второе повторение должно проверять меньше кандидатов, чем первое, хотя эта разница не существенна с точки зрения временной сложности. Оба имеют временную сложность O(𝑛²) (с табулированием динамического программирования).

Вот стресс-тест реализаций обоих в JavaScript:

function solve1(p, size) {
    const x = Array(size + 1);
    for (let n = 0; n <= size; n++) {
        x[n] = p[n];
        for (let i = n - 1; i > 0; i--) {
            x[n] = Math.max(x[n], p[i] + x[n - i]); 
        }
    }
    return x[size];
}

function solve2(p, size) {
    const x = Array(size + 1);
    for (let n = 0; n <= size; n++) {
        x[n] = p[n];
        for (let i = n >> 1; i > 0; i--) {
            x[n] = Math.max(x[n], x[i] + x[n - i]); 
        }
    }
    return x[size];
}

// Bulk test with random sampling of p for a rod of size 100.
let size = 100;
let start;
let time1 = 0, time2 = 0; // Accumulated time spent on execution
for (let test = 1; test <= 10000; test++) {
    // Define p with random values, sorted
    let p = Array.from({length: size + 1}, () => Math.floor(Math.random() * 1000))
                 .sort((a,b) => a-b);
    p[0] = 0; // This is required (in case an algorithm would read it)

    // Execute and measure the first solution:
    start = performance.now();
    let a = solve1(p, size);
    time1 += performance.now() - start;

    // Execute and measure the second solution:    
    start = performance.now();
    let b = solve2(p, size);
    time2 += performance.now() - start;
    
    // Assert that both return the same result
    console.assert(a === b, "solve1 and solve2 output different results!");
}
console.info("Milliseconds on solve1:", Math.ceil(time1));
console.info("Milliseconds on solve2:", Math.ceil(time2));