本文共 1711 字，大约阅读时间需要 5 分钟。

1. 题目

给定一个数组 A（下标从 1 开始）包含 N 个整数：A1，A2，……，AN 和一个整数 B。

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

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

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

样例 1 :输入: [1,2,4,-1,2], 2输出: [1,3,5] 样例 2 :输入: [1,2,4,-1,2], 1输出: [] 注释 :路径 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].

来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/coin-path

著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

2. 解题

class Solution {
   public:    vector
   
     cheapestJump(vector
    
     & A, int B) {
           int n = A.size(), i, len, cost, idx = n-1;        vector
     
       dp(n, INT_MAX);        vector
      
       
        > path(n);        dp[0] = A[0];        path[0] = {
   1};        for(i = 0; i < n-1; i++)         {
           	if(dp[i] == INT_MAX)//状态不存在        		continue;        	for(len = 1; len <= B; len++)        	{
           		if(i+len < n && A[i+len] != -1)//可以到达        		{
           			if(dp[i+len] > dp[i]+A[i+len])        			{
   	//取最小的花费的路径        				dp[i+len] = dp[i]+A[i+len];        				path[i+len] = path[i];        				path[i+len].push_back(i+len+1);        			}        			else if(dp[i+len] == dp[i]+A[i+len])        			{
   	//花费相同        				auto temp = path[i];        				temp.push_back(i+len+1);        				if(temp < path[i+len])//取字典序小的路径        					path[i+len] = temp;        			}        		}        	}        }        return path[n-1];    }};
       
      
     
    
   

52 ms 22 MB

我的CSDN

长按或扫码关注我的公众号（Michael阿明），一起加油、一起学习进步！

转载地址：https://michael.blog.csdn.net/article/details/107968343 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！