What is the algorithm for solving the dynamic programming problem about stairs and coins?

Question

Python

Good afternoon! I'm trying to implement an algorithm for the task:

The grasshopper jumps on columns located on the same line at equal distances from each other. The columns have serial numbers from 1 to N. At the beginning, the Grasshopper sits on column number 1. It can jump forward from 1 to K columns, counting from the current one.
On each column, the Grasshopper can gain or lose several gold coins (this number is known for each column). Determine how the Grasshopper needs to jump in order to collect the most gold coins. Keep in mind that the Grasshopper cannot jump backwards.

But I am faced with the fact that the algorithm works too slowly and not quite correctly. I would like to know how to optimize the code and where in the program I make a mistake, due to which the algorithm does not work quite correctly:

#coding=utf8

n, k = map(int, (input().split()))

stolb = list(map(int, (input().split())))

# Добавляем на 1 и последние ступени нули, т.к они без монет 
stolb.insert(0, 0)
stolb.append(0)
max_step = []

# Список с макс.кол-вом монет и список с ходами
max_money = [0]
best_step = []

for i in range(1, len(stolb)):
    i_prev_bs = i - 1
    tmp = max_money[i_prev_bs]
    for j in range(max(0, i-k), i):
        if max_money[j] > tmp:
            i_prev_bs = j
            tmp = max_money[i_prev_bs]
        
    max_money.append(tmp + stolb[i])
    best_step.append(i_prev_bs + 1)

best_step.append(n)
best_step = set(best_step)
    
print(max_money[-1])
print(len(best_step) -1)
for tmp in best_step:
    print(tmp, end=' ')

Answer 1

Heuristic optimization - you need to jump on columns with positive values ​​in a row, as soon as there are negative values ​​ahead - you need to look for a way to get to the next positive one with minimal losses.
Thus, the task is divided into equivalent subtasks of smaller volume.
It is solved by finding the optimal path in a directed graph.

Answer 2

kolomiec_artiom Adding to my comments, I took the liberty of writing an algorithm. It is similar to yours, but there are some differences that I wrote about in the comments.
Algorithm output (data inside code)

php solution.php
Steps: 1 2 4 6 9
Values: 10 20 30 -100 100000

The algorithm itself:

<?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)));