题目描述：

LeetCode 656. Coin Path

Given an array A (index starts at 1) consisting of N integers: A₁, A₂, ..., A_N and an integer B. The integer B denotes that from any place (suppose the index is i) in the array A, you can jump to any one of the place in the array A indexed i+1, i+2, …, i+B if this place can be jumped to. Also, if you step on the index i, you have to pay A_i coins. If A_i is -1, it means you can’t jump to the place indexed i in the array.

Now, you start from the place indexed 1 in the array A, and your aim is to reach the place indexed N using the minimum coins. You need to return the path of indexes (starting from 1 to N) in the array you should take to get to the place indexed N using minimum coins.

If there are multiple paths with the same cost, return the lexicographically smallest such path.

If it's not possible to reach the place indexed N then you need to return an empty array.

Example 1:

Input: [1,2,4,-1,2], 2
Output: [1,3,5]

Example 2:

Input: [1,2,4,-1,2], 1
Output: []

Note:

1. Path Pa₁, Pa₂, ..., Pa_n is lexicographically smaller than Pb₁, Pb₂, ..., Pb_m, if and only if at the first i where Pa_i and Pb_i differ, Pa_i < Pb_i; when no such i exists, then n < m.
2. A₁ >= 0. A₂, ..., A_N (if exist) will in the range of [-1, 100].
3. Length of A is in the range of [1, 1000].
4. B is in the range of [1, 100].

题目大意：

给定数组A和整数B，A表示N枚硬币的面值，-1表示硬币不存在。

从第1枚硬币出发，每次可以选择其右边的1 - B枚硬币。选择第i枚硬币的开销为A[i]

求最终选择第N枚硬币时，开销最小的选择方案；若存在并列的情况，则选择硬币标号字典序较小的方案。

解题思路：

动态规划（Dynamic Programming）

数组cost[i]表示以第i枚硬币结尾时的最小开销。

数组path[i]表示以第i枚硬币时的最佳选择方案。

若cost[i] > cost[j] + A[i] 或者 cost[i] == cost[j] + A[i] && path[i] > path[j] + [i]

则令cost[i] = cost[j] + A[i], path[i] = path[j] + [i]

Python代码：

class Solution(object):
    def cheapestJump(self, A, B):
        """
        :type A: List[int]
        :type B: int
        :rtype: List[int]
        """
        N = len(A)
        cost = [0x7FFFFFFF] * (N + 1)
        cost[1] = A[0]
        path = [[] for x in range(N + 1)]
        path[1] = [1]
        for x in range(2, N + 1):
            if A[x - 1] == -1: continue
            for y in range(1, B + 1):
                z = x - y
                if z < 1: break
                if A[z - 1] == -1: continue
                if cost[x] > cost[z] + A[x - 1] or \
                  cost[x] == cost[z] + A[x - 1] and path[x] > path[z] + [x]:
                    cost[x] = cost[z] + A[x - 1]
                    path[x] = path[z] + [x]
        return path[-1]

 

本文链接：http://bookshadow.com/weblog/2017/08/06/leetcode-coin-path/
请尊重作者的劳动成果，转载请注明出处！书影博客保留对文章的所有权利。

如果您喜欢这篇博文，欢迎您捐赠书影博客： ，查看支付宝二维码