给定一个包含 N 个整数的数组(元素为正数或 -1)和另一个整数 M。
对于每个 1 <= i <= N，我们可以跳转到数组的 i + 1, i + 2, .. i + M 索引处。从索引 1 开始，有一个线性 O(N) 算法可以找到最小成本以及到达第 N 索引的路径。其中成本是从 1 到 N 的路径中所有元素的总和。我有一个复杂度为 O(N*M) 的动态规划解决方案。
注意:如果 A[i] 为 -1，则表示我们无法降落在第 i 个索引上。
最佳答案
如果我对您的问题的理解正确，A* 可能会为您提供最佳的运行时间。对于每个 i，i+1 到 i+M 将是子节点，h 将是从 i 到 N 的成本，假设每个后续节点的成本都是 1(例如，如果 N=11 M=4 然后 h=3 for i=2，因为那将是到达最终索引所需的最小跳跃次数) .
关于algorithm - 这可以用线性时间复杂度解决吗？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/32512831/