[LeetCode]Coin Path

题目描述:

LeetCode 656. Coin Path

Given an array A (index starts at 1) consisting of N integers: A1, A2, ..., AN 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 Ai coins. If Ai 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 Pa1, Pa2, ..., Pan is lexicographically smaller than Pb1, Pb2, ..., Pbm, if and only if at the first i where Pai and Pbi differ, Pai < Pbi; when no such i exists, then n < m.
  2. A1 >= 0. A2, ..., AN (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/
请尊重作者的劳动成果,转载请注明出处!书影博客保留对文章的所有权利。

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