656. Coin Path

You are given an integer array coins (1-indexed) of length n and an integer maxJump. You can jump to any index i of the array coins if coins[i] != -1 and you have to pay coins[i] when you visit index i. In addition to that, if you are currently at index i, you can only jump to any index i + k where i + k <= n and k is a value in the range [1, maxJump].

You are initially positioned at index 1 (coins[1] is not -1). You want to find the path that reaches index n with the minimum cost.

Return an integer array of the indices that you will visit in order so that you can reach index n with the minimum cost. If there are multiple paths with the same cost, return the lexicographically smallest such path. If it is not possible to reach index n, return an empty array.

A path p1 = [Pa1, Pa2, …, Pax] of length x is lexicographically smaller than p2 = [Pb1, Pb2, …, Pbx] of length y, if and only if at the first j where Paj and Pbj differ, Paj < Pbj; when no such j exists, then x < y.

class Solution {
public:
    vector<int> cheapestJump(vector<int>& coins, int maxJump) {
        int n = coins.size();
        if(n == 1) return {1};
        vector<int> dp(n, INT_MAX);
        vector<int> path(n, -1);
        dp[n-1] = 0;
        for(int i = n - 1; i >= 0; i--) {
            if(coins[i] == -1) continue;
            for(int j = i + 1; j < min(n, i + maxJump + 1); j++) {
                if(dp[j] == INT_MAX) continue;
                if(dp[j] + coins[j] < dp[i]) {
                    dp[i] = dp[j] + coins[j];
                    path[i] = j;
                }
            }
        }
        
        if(path[0] == -1 or coins[n-1] == -1) return {};
        vector<int> res;
        int p = 0;
        while(p != -1) {
            res.push_back(p + 1);
            p = path[p];
        }
        return res;
    }
};