2022-03-06：金币路径。 给定一个数组 A（下标从 1 开始）包含 N 个整数：A1，A2，……，AN 和一个整数 B。 你可以从数组 A 中的任何一个位置（下标为 i）跳到下标 i+1，i+

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代码

2022-03-06：金币路径。 给定一个数组 A（下标从 1 开始）包含 N 个整数：A1，A2，……，AN 和一个整数 B。 你可以从数组 A 中的任何一个位置（下标为 i）跳到下标 i+1，i+的相关教程结束。