Question

656. 金币路径

English Version

题目描述

给定一个数组 A（下标从 1 开始）包含 N 个整数：A₁，A₂，……，A_N 和一个整数 B。你可以从数组 A 中的任何一个位置（下标为 i）跳到下标 i+1，i+2，……，i+B 的任意一个可以跳到的位置上。如果你在下标为 i 的位置上，你需要支付 A_i 个金币。如果 A_i 是 -1，意味着下标为 i 的位置是不可以跳到的。

现在，你希望花费最少的金币从数组 A 的 1 位置跳到 N 位置，你需要输出花费最少的路径，依次输出所有经过的下标（从 1 到 N）。

如果有多种花费最少的方案，输出字典顺序最小的路径。

如果无法到达 N 位置，请返回一个空数组。

 

样例 1 :

输入: [1,2,4,-1,2], 2
输出: [1,3,5]

 

样例 2 :

输入: [1,2,4,-1,2], 1
输出: []

 

注释 :

1. 路径 Pa₁，Pa₂，……，Pa_n 是字典序小于 Pb₁，Pb₂，……，Pb_m 的，当且仅当第一个 Pa_i 和 Pb_i 不同的 i 满足 Pa_i < Pb_i，如果不存在这样的 i 那么满足 n < m。
2. A₁ >= 0。 A₂, ..., A_N （如果存在） 的范围是 [-1, 100]。
3. A 数组的长度范围 [1, 1000].
4. B 的范围 [1, 100].

 

解法

方法一：动态规划（逆向）

题目需要我们找到从下标 1 到下标 n 的最小花费路径，且字典序最小，我们可以使用动态规划求解。

我们定义 $f[i]$ 表示从下标 $i$ 到下标 $n-1$ 的最小花费。如果 $coins[n - 1] = -1$，则不存在从下标 $n-1$ 到下标 $n-1$ 的路径，直接返回空数组即可。否则 $f[n - 1] = coins[n - 1]$。

接下来，我们从下标 $n-2$ 开始，逆向遍历数组，对于下标 $i$，如果 $coins[i] = -1$，则 $f[i] = \infty$，否则 $f[i] = \min_{j = i + 1}^{min(n - 1, i + maxJump)} f[j] + coins[i]$。

然后我们判断 $f[0]$ 是否为 $\infty$，如果是，则不存在一条满足条件的路径，返回空数组即可。否则，我们的总花费为 $s = f[0]$，我们从下标 0 开始，向后遍历数组，如果 $f[i] = s$，则说明从下标 $i$ 到下标 $n-1$ 的花费为 $s$，我们将 $s$ 减去 $coins[i]$，并将下标 $i+1$ 加入到结果数组中，直到遍历到下标 $n-1$，返回结果数组即可。

时间复杂度 $O(n \times m)$，空间复杂度 $O(n)$。其中 $n$ 和 $m$ 分别为数组的长度和最大跳跃长度。

class Solution:
  def cheapestJump(self, coins: List[int], maxJump: int) -> List[int]:
    if coins[-1] == -1:
      return []
    n = len(coins)
    f = [inf] * n
    f[-1] = coins[-1]
    for i in range(n - 2, -1, -1):
      if coins[i] != -1:
        for j in range(i + 1, min(n, i + maxJump + 1)):
          if f[i] > f[j] + coins[i]:
            f[i] = f[j] + coins[i]
    if f[0] == inf:
      return []
    ans = []
    s = f[0]
    for i in range(n):
      if f[i] == s:
        s -= coins[i]
        ans.append(i + 1)
    return ans

class Solution {
  public List<Integer> cheapestJump(int[] coins, int maxJump) {
    int n = coins.length;
    List<Integer> ans = new ArrayList<>();
    if (coins[n - 1] == -1) {
      return ans;
    }
    int[] f = new int[n];
    final int inf = 1 << 30;
    Arrays.fill(f, inf);
    f[n - 1] = coins[n - 1];
    for (int i = n - 2; i >= 0; --i) {
      if (coins[i] != -1) {
        for (int j = i + 1; j < Math.min(n, i + maxJump + 1); ++j) {
          if (f[i] > f[j] + coins[i]) {
            f[i] = f[j] + coins[i];
          }
        }
      }
    }
    if (f[0] == inf) {
      return ans;
    }
    for (int i = 0, s = f[0]; i < n; ++i) {
      if (f[i] == s) {
        s -= coins[i];
        ans.add(i + 1);
      }
    }
    return ans;
  }
}

class Solution {
public:
  vector<int> cheapestJump(vector<int>& coins, int maxJump) {
    int n = coins.size();
    vector<int> ans;
    if (coins[n - 1] == -1) {
      return ans;
    }
    int f[n];
    const int inf = 1 << 30;
    f[n - 1] = coins[n - 1];
    for (int i = n - 2; ~i; --i) {
      f[i] = inf;
      if (coins[i] != -1) {
        for (int j = i + 1; j < min(n, i + maxJump + 1); ++j) {
          f[i] = min(f[i], f[j] + coins[i]);
        }
      }
    }
    if (f[0] == inf) {
      return ans;
    }
    for (int i = 0, s = f[0]; i < n; ++i) {
      if (f[i] == s) {
        s -= coins[i];
        ans.push_back(i + 1);
      }
    }
    return ans;
  }
};

func cheapestJump(coins []int, maxJump int) (ans []int) {
  n := len(coins)
  if coins[n-1] == -1 {
    return
  }
  f := make([]int, n)
  f[n-1] = coins[n-1]
  const inf = 1 << 30
  for i := n - 2; i >= 0; i-- {
    f[i] = inf
    if coins[i] != -1 {
      for j := i + 1; j < n && j < i+maxJump+1; j++ {
        if f[i] > f[j]+coins[i] {
          f[i] = f[j] + coins[i]
        }
      }
    }
  }
  if f[0] == inf {
    return
  }
  for i, s := 0, f[0]; i < n; i++ {
    if f[i] == s {
      s -= coins[i]
      ans = append(ans, i+1)
    }
  }
  return
}

function cheapestJump(coins: number[], maxJump: number): number[] {
  const n = coins.length;
  const ans: number[] = [];
  if (coins[n - 1] == -1) {
    return ans;
  }
  const inf = 1 << 30;
  const f: number[] = new Array(n).fill(inf);
  f[n - 1] = coins[n - 1];
  for (let i = n - 2; i >= 0; --i) {
    if (coins[i] !== -1) {
      for (let j = i + 1; j < Math.min(n, i + maxJump + 1); ++j) {
        f[i] = Math.min(f[i], f[j] + coins[i]);
      }
    }
  }
  if (f[0] === inf) {
    return ans;
  }
  for (let i = 0, s = f[0]; i < n; ++i) {
    if (f[i] == s) {
      s -= coins[i];
      ans.push(i + 1);
    }
  }
  return ans;
}