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

😎 Решение:

using System;
using System.Collections.Generic;

public class Solution {
    public List<int> MinCostPath(int[] coins, int maxJump) {
        int n = coins.Length;
        if (coins[0] == -1) return new List<int>();
        
        int[] dp = new int[n];
        Array.Fill(dp, int.MaxValue);
        dp[0] = coins[0];
        List<int>[] path = new List<int>[n];
        for (int i = 0; i < n; i++) path[i] = new List<int>();
        path[0].Add(1);
        
        PriorityQueue<(int cost, int index), int> heap = new PriorityQueue<(int, int), int>();
        heap.Enqueue((coins[0], 0), coins[0]);
        
        while (heap.Count > 0) {
            var (currentCost, i) = heap.Dequeue();
            if (currentCost > dp[i]) continue;
            for (int k = 1; k <= maxJump; k++) {
                if (i + k < n && coins[i + k] != -1) {
                    int newCost = currentCost + coins[i + k];
                    if (newCost < dp[i + k] || (newCost == dp[i + k] && ComparePaths(path[i], path[i + k], i + k + 1))) {
                        dp[i + k] = newCost;
                        path[i + k] = new List<int>(path[i]);
                        path[i + k].Add(i + k + 1);
                        heap.Enqueue((newCost, i + k), newCost);
                    }
                }
            }
        }
        
        return dp[n - 1] == int.MaxValue ? new List<int>() : path[n - 1];
    }

    private bool ComparePaths(List<int> path1, List<int> path2, int newIndex) {
        List<int> newPath1 = new List<int>(path1);
        newPath1.Add(newIndex);
        return string.Join(",", newPath1).CompareTo(string.Join(",", path2)) < 0;
    }

    public static void Main(string[] args) {
        Solution solution = new Solution();
        int[] coins = { 0, 2, 4, -1, 2, 5 };
        int maxJump = 2;
        var result = solution.MinCostPath(coins, maxJump);
    }
}

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