Динамическое программирование на JS

Question

для игры необходимо реализовать алгоритм на js: Игрок находятся на нулевой платформе. Ему нужно дойти до платформы N. Игрок может прыгать или на следующую платформу, или через одну. Если игрок прыгает на соседнюю платформу он тратит |y2 - y1| энергии, а если через одну то 3 * |y3 - y1|, где yn - высота n-платформы. Нужно найти минимальное количество энергии, чтобы игрок добрался до платформы N.

Я начал пытаться писать данный алгоритм, но застрял в тупике.

var maxPlatforms = round(10);
var remainder = maxPlatforms % 2;
var energy = 3 * ((maxPlatforms - remainder) / 2);

if(remainder > 0) {
    energy = energy + 2;
};

return energy

Заранее спасибо.

Answer 1

ЗатраченоЭнергии = 0
Пока текущаяПлатформа < N цикл
  // Определить какой из вариантов менее затратен по энергии
  Если ПрыжокНаСледующую() < ПрыжокЧерезОдну() Тогда
     ЗатраченоЭнергии += ПрыжокНаСледующую()
     текущаяПлатформа += 1
  Иначе
     ЗатраченоЭнергии += ПрыжокЧерезОдну()
     текущаяПлатформа += 2
  КонецЕсли
КонецЦикла

Answer 2

Начните с конца. Попасть на n-ю платформу можно с предпоследней или с предпредпоследней, так что

F(N) = Min(F(N-1) + abs(y(n)-y(n-1)),  F(N-2) + 3*abs(y(n)-y(n-2)))

Рекурсивно решайте до нулевой платформы. Когда всё заработает, можно преобразовать в динамическое программирование (мемоизация), запоминая лучшие варианты для каждой платформы.

БЛОГ НА HUSL

Динамическое программирование на JS

Ответы (2 шт):