# 656. Coin Path

## Approach 1: Top-down

• Time: $O(n \cdot \texttt{maxJump})$
• Space: $O(n)$
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 class Solution { public: vector cheapestJump(vector& coins, int maxJump) { if (coins.back() == -1) return {}; const int n = coins.size(); vector next(n, -1); // dp[i] := min cost to jump from i to n - 1 dp.resize(n, INT_MAX); cheapestJump(coins, maxJump, 0, next); if (dp[0] == INT_MAX) return {}; return constructPath(next, 0); } private: vector dp; int cheapestJump(const vector& coins, int maxJump, int i, vector& next) { if (i == coins.size() - 1) return dp[i] = coins[i]; if (dp[i] < INT_MAX) return dp[i]; if (coins[i] == -1) return INT_MAX; for (int j = i + 1; j <= i + maxJump && j < coins.size(); ++j) { const int res = cheapestJump(coins, maxJump, j, next); if (res == INT_MAX) continue; const int cost = coins[i] + res; if (cost < dp[i]) { dp[i] = cost; next[i] = j; } } return dp[i]; } vector constructPath(const vector& next, int i) { vector ans; while (i != -1) { ans.push_back(i + 1); // 1-indexed i = next[i]; } return ans; } }; 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 class Solution { public List cheapestJump(int[] coins, int maxJump) { if (coins[coins.length - 1] == -1) return new ArrayList<>(); final int n = coins.length; int[] next = new int[n]; Arrays.fill(next, -1); // dp[i] := min cost to jump from i to n - 1 dp = new int[n]; Arrays.fill(dp, Integer.MAX_VALUE); cheapestJump(coins, maxJump, 0, next); if (dp[0] == Integer.MAX_VALUE) return new ArrayList<>(); return constructPath(next, 0); } private int[] dp; private int cheapestJump(int[] coins, int maxJump, int i, int[] next) { if (i == coins.length - 1) return dp[i] = coins[i]; if (dp[i] < Integer.MAX_VALUE) return dp[i]; if (coins[i] == -1) return Integer.MAX_VALUE; for (int j = i + 1; j < Math.min(i + maxJump + 1, coins.length); ++j) { final int res = cheapestJump(coins, maxJump, j, next); if (res == Integer.MAX_VALUE) continue; final int cost = coins[i] + res; if (cost < dp[i]) { dp[i] = cost; next[i] = j; } } return dp[i]; } private List constructPath(int[] next, int i) { List ans = new ArrayList<>(); while (i != -1) { ans.add(i + 1); // 1-indexed i = next[i]; } return ans; } } 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 class Solution: def cheapestJump(self, coins: List[int], maxJump: int) -> List[int]: if coins[-1] == -1: return [] n = len(coins) # dp[i] := min cost to jump from i to n - 1 dp = [math.inf] * n next = [-1] * n def cheapestJump(i: int) -> int: if i == len(coins) - 1: dp[i] = coins[i] return dp[i] if dp[i] < math.inf: return dp[i] if coins[i] == -1: return math.inf for j in range(i + 1, min(i + maxJump + 1, n)): res = cheapestJump(j) if res == math.inf: continue cost = coins[i] + res if cost < dp[i]: dp[i] = cost next[i] = j return dp[i] cheapestJump(0) if dp[0] == math.inf: return [] return self._constructPath(next, 0) def _constructPath(self, next: List[int], i: int) -> List[int]: ans = [] while i != -1: ans.append(i + 1) # 1-indexed i = next[i] return ans 

## Approach 2: Bottom-up

• Time: $O(n \cdot \texttt{maxJump})$
• Space: $O(n)$
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 class Solution { public: vector cheapestJump(vector& coins, int maxJump) { if (coins.back() == -1) return {}; const int n = coins.size(); // dp[i] := min cost to jump to n - 1 from i vector dp(n, INT_MAX); vector next(n, -1); dp.back() = coins.back(); for (int i = n - 2; i >= 0; --i) { if (coins[i] == -1) continue; for (int j = i + 1; j < min(i + maxJump + 1, n); ++j) { if (dp[j] == INT_MAX) continue; const int cost = coins[i] + dp[j]; if (cost < dp[i]) { dp[i] = cost; next[i] = j; } } } if (dp[0] == INT_MAX) return {}; return constructPath(next, 0); } private: vector constructPath(const vector& next, int i) { vector ans; while (i != -1) { ans.push_back(i + 1); // 1-indexed i = next[i]; } return ans; } }; 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 class Solution { public List cheapestJump(int[] coins, int maxJump) { if (coins[coins.length - 1] == -1) return new ArrayList<>(); final int n = coins.length; // dp[i] := min cost to jump from i to n - 1 int[] dp = new int[n]; int[] next = new int[n]; Arrays.fill(dp, Integer.MAX_VALUE); Arrays.fill(next, -1); dp[n - 1] = coins[n - 1]; for (int i = n - 2; i >= 0; --i) { if (coins[i] == -1) continue; for (int j = i + 1; j < Math.min(i + maxJump + 1, n); ++j) { if (dp[j] == Integer.MAX_VALUE) continue; final int cost = coins[i] + dp[j]; if (cost < dp[i]) { dp[i] = cost; next[i] = j; } } } if (dp[0] == Integer.MAX_VALUE) return new ArrayList<>(); return constructPath(next, 0); } private List constructPath(int[] next, int i) { List ans = new ArrayList<>(); while (i != -1) { ans.add(i + 1); // 1-indexed i = next[i]; } return ans; } } 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 class Solution: def cheapestJump(self, coins: List[int], maxJump: int) -> List[int]: if coins[-1] == -1: return [] n = len(coins) # dp[i] := min cost to jump to n - 1 from i dp = [math.inf] * n next = [-1] * n dp[-1] = coins[-1] for i in reversed(range(n - 1)): if coins[i] == -1: continue for j in range(i + 1, min(i + maxJump + 1, n)): if dp[j] == math.inf: continue cost = coins[i] + dp[j] if cost < dp[i]: dp[i] = cost next[i] = j if dp[0] == math.inf: return [] return self._constructPath(next, 0) def _constructPath(self, next: List[int], i: int) -> List[int]: ans = [] while i != -1: ans.append(i + 1) # 1-indexed i = next[i] return ans