Approach 1: Top-down

• Time:O(n \cdot \texttt{maxJump})
• Space:O(n)

C++

class Solution {
public:
vector<int> cheapestJump(vector<int>& coins, int maxJump) {
if (coins.back() == -1)
return {};

const int n = coins.size();
vector<int> 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<int> dp;

int cheapestJump(const vector<int>& coins, int maxJump, int i,
vector<int>& 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<int> constructPath(const vector<int>& next, int i) {
vector<int> ans;
while (i != -1) {
ans.push_back(i + 1);  // 1-indexed
i = next[i];
}
return ans;
}
};


JAVA

class Solution {
public List<Integer> 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<Integer> constructPath(int[] next, int i) {
List<Integer> ans = new ArrayList<>();
while (i != -1) {
i = next[i];
}
return ans;
}
}


Python

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)

C++

class Solution {
public:
vector<int> cheapestJump(vector<int>& 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<int> dp(n, INT_MAX);
vector<int> 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<int> constructPath(const vector<int>& next, int i) {
vector<int> ans;
while (i != -1) {
ans.push_back(i + 1);  // 1-indexed
i = next[i];
}
return ans;
}
};


JAVA

class Solution {
public List<Integer> 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<Integer> constructPath(int[] next, int i) {
List<Integer> ans = new ArrayList<>();
while (i != -1) {
i = next[i];
}
return ans;
}
}


Python

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