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

Вам дан целочисленный массив монет (1-индексированный) длины n и целое число maxJump. Вы можете перейти на любой индекс i массива coins, если coins[i] != -1 и вы должны заплатить coins[i] при посещении индекса i. Кроме того, если вы в данный момент находитесь на индексе i, вы можете перейти только на любой индекс i + k, где i + k <= n и k - значение в диапазоне [1, maxJump]. Изначально вы находитесь на индексе 1 (coins[1] не -1). Вы хотите найти путь, который достигнет индекса n с минимальной стоимостью. Верните целочисленный массив индексов, которые вы посетите в таком порядке, чтобы достичь индекса n с минимальной стоимостью. Если существует несколько путей с одинаковой стоимостью, верните лексикографически наименьший такой путь. Если невозможно достичь индекса n, возвращается пустой массив. Путь p1 = [Pa1, Pa2, ..., Pax] длины x лексикографически меньше, чем p2 = [Pb1, Pb2, ..., Pbx] длины y, если и только если при первом j, где Paj и Pbj отличаются, Paj < Pbj; если такого j нет, то x < y.

Пример:

Input: coins = [1,2,4,-1,2], maxJump = 2
Output: [1,3,5]

👨‍💻 Алгоритм:

1⃣Используйте динамическое программирование для нахождения минимальной стоимости до каждого индекса, начиная с первого.

2⃣Храните путь до каждого индекса для отслеживания наименьшего лексикографического пути.

3⃣Используя полученную информацию, восстановите путь с минимальной стоимостью до последнего индекса.

😎 Решение:

function minCostPath($coins, $maxJump) {
    $n = count($coins);
    if ($coins[0] == -1) return [];
    
    $dp = array_fill(0, $n, PHP_INT_MAX);
    $dp[0] = $coins[0];
    $path = array_fill(0, $n, []);
    $path[0] = [1];
    
    $heap = new SplPriorityQueue();
    $heap->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 <= $maxJump; $k++) {
            if ($i + $k < $n && $coins[$i + $k] != -1) {
                $new_cost = $current_cost + $coins[$i + $k];
                if ($new_cost < $dp[$i + $k] || ($new_cost == $dp[$i + $k] && $path[$i] < array_merge($path[$i], [$i + $k + 1]))) {
                    $dp[$i + $k] = $new_cost;
                    $path[$i + $k] = array_merge($path[$i], [$i + $k + 1]);
                    $heap->insert([$new_cost, $i + $k], -$new_cost);
                }
            }
        }
    }
    
    return $dp[$n - 1] == PHP_INT_MAX ? [] : $path[$n - 1];
}

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