⚡Flashcard Drill➔
NeetCode #711LC-656Hard1-D Dynamic Programming
← Back to All Problems

#711 · #656 · Coin Path(金币路径)

📌 Problem Statement & Constraints

Given an integer array coins, where 0 marks a position you may not land on, and an integer maxJump, find a path from index 0 to index n - 1 in which each jump advances between 1 and maxJump positions and the total cost (the sum of landed coins, including both endpoints) is minimised. Return the path as a list of 1-indexed positions, or an empty list if none exists. Constraints: 1 <= n <= 1000, 0 <= coins[i] <= 10^4, 1 <= maxJump <= 1000.

💡 Core Algorithmic Approaches

  1. dp[i] is the minimum cost to reach the end from index i, with dp[n-1] = coins[n-1].
  2. For each i from right to left, dp[i] = coins[i] + min(dp[i+j]) over j in 1..maxJump with a landable i+j.
  3. dp[i] stays infinite when no landing is possible, which propagates unreachability to the start.
  4. Reconstruct the path by always stepping to the neighbour with the smallest dp, breaking ties toward the smallest index.

💻 Benchmark Python3 Implementation

class Solution:
    def cheapestJump(self, coins: List[int], maxJump: int) -> List[int]:
        n = len(coins)
        if coins[n - 1] == 0:
            return []                  # the destination is not landable
        INF = float("inf")
        dp = [INF] * n
        nxt = [-1] * n
        dp[n - 1] = coins[n - 1]
        for i in range(n - 2, -1, -1):
            if coins[i] == 0:
                continue
            for j in range(i + 1, min(i + maxJump, n - 1) + 1):
                if dp[j] < dp[i]:
                    dp[i] = dp[j]
                    nxt[i] = j         # smallest j wins ties
            if dp[i] != INF:
                dp[i] += coins[i]
        if dp[0] == INF:
            return []
        res = []
        i = 0
        while i != -1:
            res.append(i + 1)          # the answer is 1-indexed
            i = nxt[i]
        return res

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(n * maxJump): each index scans up to maxJump successors.
💾 Space Complexity
O(n): the dp and nxt arrays.

⚠️ Interview Pitfalls & Follow-ups

  • Returning 0-indexed positions: LeetCode 656 expects 1-indexed indices.
  • Omitting the coins[-1] == 0 early return: the destination must be landable.
  • Allowing a jump of 0: every jump advances at least one index, so the successor loop starts at i + 1.
  • Breaking ties toward the largest index: iterating j upward with a strict < keeps the lexicographically smallest path.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.
🎯 Drill This Card Now➔

🧩 Related 1-D Dynamic Programming Problems