656.金幣路徑

給定一個數組?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]

樣例 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/problems/coin-path
著作權歸領扣網絡所有。商業轉載請聯系官方授權，非商業轉載請注明出處。

做題結果

寫出，但是不太好，動態規劃+DFS

方法：動態規劃+DFS

1. 動態規劃算出最小步數是幾，記錄每個節點

2. dfs查找字典序最小的結果

class Solution {public List<Integer> cheapestJump(int[] coins, int maxJump) {int n = coins.length;int[] minSpend = new int[n];Arrays.fill(minSpend,Integer.MAX_VALUE);minSpend[0] = coins[0];for(int i = 0; i < n-1; i++){if(minSpend[i]==Integer.MAX_VALUE) continue;for(int j = 1; j <= maxJump&&i+j<n; j++){if(coins[i+j]==-1) continue;minSpend[i+j] = Math.min(minSpend[i]+coins[i+j],minSpend[i+j]);}}if(minSpend[n-1]==Integer.MAX_VALUE) return ans;;test(minSpend,coins,new ArrayList<>(),n-1,maxJump);return ans;}List<Integer> ans = new ArrayList<>();private void test(int[] dp, int[] coins, List<Integer> curr,int pos,int maxJump){if(pos == 0){curr.add(1);Collections.reverse(curr);if(cmp(curr)<0)ans = new ArrayList<>(curr);Collections.reverse(curr);curr.remove(curr.size()-1);return;}curr.add(pos+1);int v = dp[pos]-coins[pos];for(int j = 1; j <= maxJump&&pos-j>=0; j++){if(dp[pos-j]==v) {test(dp,coins,curr,pos-j,maxJump);}}curr.remove(curr.size()-1);}private int cmp(List<Integer> curr){if(ans.isEmpty()) return -1;int s1 = ans.size();int s2 = curr.size();for(int i = 0; i < Math.min(s1,s2); i++){if(curr.get(i).compareTo(ans.get(i))!=0){return curr.get(i).compareTo(ans.get(i));}}return s2-s1;}}

總結

以上是生活随笔為你收集整理的力扣 656.金币路径的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。