Skip to content

656. Coin Path

Approach 1: Top-down

  • Time: $O(n \cdot \texttt{maxJump})$
  • Space: $O(n)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
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;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
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;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
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)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
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;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
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;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
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