#ЛитКод
Задача: 656. Coin Path

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

😎 Решение:

var minCostPath = function(coins, maxJump) {
    const n = coins.length;
    if (coins[0] === -1) return [];
    
    const dp = new Array(n).fill(Infinity);
    dp[0] = coins[0];
    const path = Array.from({ length: n }, () => []);
    path[0] = [1];
    
    const heap = [[coins[0], 0]];
    
    while (heap.length) {
        heap.sort((a, b) => a[0] - b[0]);
        const [current_cost, i] = heap.shift();
        if (current_cost > dp[i]) continue;
        for (let k = 1; k <= maxJump; k++) {
            if (i + k < n && coins[i + k] !== -1) {
                const new_cost = current_cost + coins[i + k];
                if (new_cost < dp[i + k] || (new_cost === dp[i + k] && path[i].concat(i + k + 1) < path[i + k])) {
                    dp[i + k] = new_cost;
                    path[i + k] = path[i].concat(i + k + 1);
                    heap.push([new_cost, i + k]);
                }
            }
        }
    }
    
    return dp[n - 1] === Infinity ? [] : path[n - 1];
};

👉Новости 👉База вопросов