Coin Path - Leetcode

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

          

        

      
     

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) {
      ans.add(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) { ans.add(i + 1); // 1-indexed 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

          

        

      
     

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

          

        

      
     

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) {
      ans.add(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) { ans.add(i + 1); // 1-indexed 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

          

        

      
     