Задача: 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⃣Используя полученную информацию, восстановите путь с минимальной стоимостью до последнего индекса.

😎 Решение:

import Foundation

func minCostPath(_ coins: [Int], _ maxJump: Int) -> [Int] {
    let n = coins.count
    if coins[0] == -1 { return [] }
    
    var dp = [Int](repeating: Int.max, count: n)
    dp[0] = coins[0]
    var path = Array(repeating: [Int](), count: n)
    path[0] = [1]
    
    var heap = [(cost: Int, index: Int)]()
    heap.append((coins[0], 0))
    
    while !heap.isEmpty {
        heap.sort(by: { $0.cost < $1.cost })
        let (current_cost, i) = heap.removeFirst()
        if current_cost > dp[i] { continue }
        for k in 1...maxJump {
            if i + k < n && coins[i + k] != -1 {
                let new_cost = current_cost + coins[i + k]
                if new_cost < dp[i + k] || (new_cost == dp[i + k] && path[i] + [i + k + 1] < path[i + k]) {
                    dp[i + k] = new_cost
                    path[i + k] = path[i] + [i + k + 1]
                    heap.append((new_cost, i + k))
                }
            }
        }
    }
    
    return dp[n - 1] == Int.max ? [] : path[n - 1]
}

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