Задача: 656. Coin Path
Сложность: hard

Вам дан целочисленный массив монет (1-индексированный) длины n и целое число maxJump. Вы можете перейти на любой индекс i массива coins, если coins[i] != -1 и вы должны заплатить coins[i] при посещении индекса i. Кроме того, если вы в данный момент находитесь на индексе i, вы можете перейти только на любой индекс i + k, где i + k setExtractFlags(SplPriorityQueue::EXTR_BOTH);
$heap->insert([0, 0], -$coins[0]);

while (!$heap->isEmpty()) {
$current = $heap->extract();
$current_cost = -$current['priority'];
$i = $current['data'][1];
if ($current_cost > $dp[$i]) continue;
for ($k = 1; $k insert([$new_cost, $i + $k], -$new_cost);
}
}
}
}

return $dp[$n - 1] == PHP_INT_MAX ? [] : $path[$n - 1];
}

Ставь 👍 и забирай 📚 Базу знаний