Задача динамического программирования справки. Максимизация суммы ступеней при заданном количестве шагов

Question

Мне нужно создать решение динамического программирования для следующей задачи:

Учитывая набор из n ступеней, так что каждый шаг ступени имеет положительное значение, как мы можем максимизировать значение, если нам разрешеноk поднимается по лестнице, и мы можем пропустить 1 или 2 шага за раз

Пример:

Дано обр. 5, 1, 6, 2, 8, 9 n = 6

k = 3 мы бы взяли 6,8,9

k = 2 мы бы взяли 6,9

k = 1 мы не смогли бы добраться до вершиныЛестница, самая дальняя, которую мы могли бы получить, это оценить 6

k = n, мы бы сделали все шаги

Что сбивает меня с толку, так это то, что вы должны принятьпоследнее значение (чтобы добраться до вершины лестницы), и вы должны принимать значения таким образом, чтобы вы могли действительно достичь конца. Спасибо за любую помощь или указатели в правильном направлении, спасибо!

Обновление:

Я смог кешировать рекурсивные вызовы и достигнуть O (n * k), не зная, какдостичь решения DP здесь.

int myMem(int arr[], int n, int L)
{
count += 1;
if (L == 0 && n < 1)
    return 0;

if (L == n/3)
{
  if(mem[n-1][L] == 0)
    mem[n-1][L] = myMem(arr, n-3, L-1);
  return arr[n-1] + mem[n-1][L];
}

if (n < 1)
    return INT_MIN;

if (L > n/3)
{
    if(mem[n-1][L] == 0)
        mem[n-1][L] = myMax( myMem(arr, n-1, L-1), myMem(arr, n-2, L-1), myMem(arr, n-3, L-1));

    return arr[n-1] + mem[n-1][L];
}
return INT_MIN;
}

Answer 1

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

Нисходящий код JavaScript без запоминания (bottom-вверх до читателя):

function f(A, n, k){
  if (k == 0 && n < 1)
    return 0

  if (k == n / 3)
    return A[n-1] + f(A, n - 3, k - 1)

  if (n < 1)
    return -Infinity

  if (k > n / 3){
    return A[n-1] + Math.max(
      f(A, n - 1, k - 1),
      f(A, n - 2, k - 1),
      f(A, n - 3, k - 1)
    )
  }

  return -Infinity
}

var A = [5, 1, 6, 2, 8, 9]
var n = A.length
var k = 3

console.log(`A: ${A}`)
console.log(`k: ${k}`)
console.log(`max of (${f(A, n, k)}, ${f(A, n - 1, k)}, ${f(A, n - 2, k)})`)
console.log('')

k = 2

console.log(`k: ${k}`)
console.log(`max of (${f(A, n, k)}, ${f(A, n - 1, k)}, ${f(A, n - 2, k)})`)
console.log('')

k = 1

console.log(`k: ${k}`)
console.log(`max of (${f(A, n, k)}, ${f(A, n - 1, k)}, ${f(A, n - 2, k)})`)