Какой алгоритм для решения задачи на динамическое программирование про лестницу и монеты?
Эвристическая оптимизация - по столбикам с положительными значениями надо прыгать подряд, как только впереди отрицательные значения - надо искать способ попасть на следующее положительное с минимальными потерями.
Таким образом задача разбивается на эквивалентные подзадачи меньшего объёма.
Решается поиском оптимального пути в ориентированном графе.
kolomiec_artiom Добавляя к своим комментариям, позволил себе написать алгоритм. Он схож с вашим, но есть некоторые отличия о которых я писал в комментариях. 
Вывод алгоритма (данные внутри кода)php solution.php
Steps: 1 2 4 6 9
Values: 10 20 30 -100 100000
Сам алгоритм:<?php

$k = 3;
$weight = [1 => 10, 20, -5, 30, -5, -100, -3000, -5000, 100000];
$n = count($weight);

$sum = [];
$comeFrom = [];

$sum[0] = 0;
$comeFrom[0] = 0;

for ($i = 1; $i <= $n; $i++) {
    $comeFromIndex = $i - 1;
    for ($j = max(0, $i - $k); $j <= ($i - 1); $j++) {
        if ($sum[$j] > $sum[$comeFromIndex]) {
            $comeFromIndex = $j;
        }
    }

    $sum[$i] = $sum[$comeFromIndex] + $weight[$i];
    $comeFrom[$i] = $comeFromIndex;
}

$steps = [];
while ($n) {
    $steps[] = $n;
    $n = $comeFrom[$n];
}

echo 'Steps: ' . implode(' ', array_reverse($steps));
echo "\n";
echo 'Values: ' . implode(' ', array_intersect_key($weight, array_combine($steps, $steps)));