[0656] 金币路径

• GitHub
• http://leetcode.xuezhisd.top/post/91be09d.html
• https://leetcode.com/problems/coin-path
• https://leetcode-cn.com/problems/coin-path

题目描述

给定一个数组 A（下标从 1 开始）包含 N 个整数：A₁，A₂，……，A_N 和一个整数 B。你可以从数组 A 中的任何一个位置（下标为 i）跳到下标 i+1，i+2，……，i+B 的任意一个可以跳到的位置上。如果你在下标为 i 的位置上，你需要支付 A_i 个金币。如果 A_i 是 -1，意味着下标为 i 的位置是不可以跳到的。

现在，你希望花费最少的金币从数组 A 的 1 位置跳到 N 位置，你需要输出花费最少的路径，依次输出所有经过的下标（从 1 到 N）。

如果有多种花费最少的方案，输出字典顺序最小的路径。

如果无法到达 N 位置，请返回一个空数组。

 

样例 1 :

输入: [1,2,4,-1,2], 2
输出: [1,3,5]

 

样例 2 :

输入: [1,2,4,-1,2], 1
输出: []

 

注释 :

1. 路径 Pa₁，Pa₂，……，Pa_n 是字典序小于 Pb₁，Pb₂，……，Pb_m 的，当且仅当第一个 Pa_i 和 Pb_i 不同的 i 满足 Pa_i < Pb_i，如果不存在这样的 i 那么满足 n < m。
2. A₁ >= 0。 A₂, ..., A_N （如果存在） 的范围是 [-1, 100]。
3. A 数组的长度范围 [1, 1000].
4. B 的范围 [1, 100].

 

Related Topics

动态规划

题目解析

• [请一句话描述题目…]

不确定性

方法一：[算法名称]

分析

思路

注意

知识点

复杂度

代码

//

方法二：[算法名称]

分析

思路

注意

知识点

复杂度

代码

//

相关题目