2022-03-06：金币路径。 给定一个数组 A（下标从 1 开始）包含 N 个整数：A1，A2，……，AN 和一个整数 B。 你可以从数组 A 中的任何一个位置（下标为 i）跳到下标 i+1，i+2，……，i+B 的任意一个可以跳到的位置上。 如果你在下标为 i 的位置上，你需要支付 Ai 个金币。 如果 Ai 是 -1，意味着下标为 i 的位置是不可以跳到的。 现在，你希望花费最少的金币从数组 A 的 1 位置跳到 N 位置，你需要输出花费最少的路径，依次输出所有经过的下标（从 1 到 N）。 如果有多种花费最少的方案，输出字典顺序最小的路径。 如果无法到达 N 位置，请返回一个空数组。 样例 1 : 输入: [1,2,4,-1,2], 2 输出: [1,3,5] 注释 : 路径 Pa1，Pa2，……，Pan 是字典序小于 Pb1，Pb2，……，Pbm 的， 当且仅当第一个 Pai 和 Pbi 不同的 i 满足 Pai < Pbi， 如果不存在这样的 i 那么满足 n < m。 A1 >= 0。 A2, ..., AN （如果存在） 的范围是 [-1, 100]。 A 数组的长度范围 [1, 1000]. B 的范围 [1, 100]. 力扣656。

答案2022-03-06：

时间紧，具体见代码。

代码用python编写。代码如下：

# -*-coding:utf-8-*-
# Time:  O(n * B)
# Space: O(n)
class Solution(object):
    def cheapestJump(self, A, B):
        """
        :type A: List[int]
        :type B: int
        :rtype: List[int]
        """
        result = []
        if not A or A[-1] == -1:
            return result
        n = len(A)
        dp, next_pos = [float("inf")] * n, [-1] * n
        dp[n-1] = A[n-1]
        for i in reversed(range(n-1)):
            if A[i] == -1:
                continue
            for j in range(i+1, min(i+B+1,n)):
                if A[i] + dp[j] < dp[i]:
                    dp[i] = A[i] + dp[j]
                    next_pos[i] = j
        if dp[0] == float("inf"):
            return result
        k = 0
        while k != -1:
            result.append(k+1)
            k = next_pos[k]
        return result

if __name__ == '__main__':
    obj = Solution();
    A = [1,2,4,-1,2];
    B = 2;
    C = obj.cheapestJump(A,B);
    print(C);

执行结果如下： 在这里插入图片描述

左神java代码