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
dp[i]is the minimum cost to reach the end from indexi, withdp[n-1] = coins[n-1].- For each
ifrom right to left,dp[i] = coins[i] + min(dp[i+j])overjin1..maxJumpwith a landablei+j. dp[i]stays infinite when no landing is possible, which propagates unreachability to the start.- 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] == 0early 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
jupward 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.