LeetCode Solutions

			

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;
  }
};

			

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) {
      ans.add(i + 1); // 1-indexed
      i = next[i];
    }
    return ans;
  }
}

			

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