Задача: 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 java.util.*;

class Solution {
    public List<Integer> minCostPath(int[] coins, int maxJump) {
        int n = coins.length;
        if (coins[0] == -1) return new ArrayList<>();
        
        int[] dp = new int[n];
        Arrays.fill(dp, Integer.MAX_VALUE);
        dp[0] = coins[0];
        List<Integer>[] path = new List[n];
        for (int i = 0; i < n; i++) path[i] = new ArrayList<>();
        path[0].add(1);
        
        PriorityQueue<int[]> heap = new PriorityQueue<>(Comparator.comparingInt(a -> a[0]));
        heap.offer(new int[] { coins[0], 0 });
        
        while (!heap.isEmpty()) {
            int[] current = heap.poll();
            int current_cost = current[0], i = current[1];
            if (current_cost > dp[i]) continue;
            for (int k = 1; k <= maxJump; k++) {
                if (i + k < n && coins[i + k] != -1) {
                    int new_cost = current_cost + coins[i + k];
                    if (new_cost < dp[i + k] || (new_cost == dp[i + k] && comparePaths(path[i], path[i + k], i + k + 1))) {
                        dp[i + k] = new_cost;
                        path[i + k] = new ArrayList<>(path[i]);
                        path[i + k].add(i + k + 1);
                        heap.offer(new int[] { new_cost, i + k });
                    }
                }
            }
        }
        
        return dp[n - 1] == Integer.MAX_VALUE ? new ArrayList<>() : path[n - 1];
    }
    
    private boolean comparePaths(List<Integer> path1, List<Integer> path2, int newIndex) {
        List<Integer> newPath1 = new ArrayList<>(path1);
        newPath1.add(newIndex);
        return newPath1.toString().compareTo(path2.toString()) < 0;
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        int[] coins = {0, 2, 4, -1, 2, 5};
        int maxJump = 2;
}

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