寻找增加元素值的最小跳跃次数

Question

优化一个 leetcode 风格的问题 - DP/DFS

任务如下：

给定N个高度，找出从头到尾所需的最小次优跳跃次数。 [一维数组]
如果起点 i 的高度小于或等于目标点 j 的高度，则跳跃是次优的。
如果 j-i >= k，则可以跳跃，其中 k 是最大跳跃距离。
对于第一个子任务，只有一个k值。
对于第二个子任务，有两个k值；输出每个 k 值的次优跳跃量。
对于第三个子任务，有100k个值；输出每个 k 值的次优跳跃量。

我的尝试

以下代码片段是我解决问题的方法，它给出了正确的解决方案。

这已经过优化，可以处理多个 k 值，而无需做很多不必要的工作。问题在于，即使是具有单个 k 值的解决方案在最坏的情况下也是 o(n^2) 。（当 k <= N）一个解决方案是消除嵌套的 for 循环，这是我不确定如何处理它的问题。

def solve(testcase):
    N, Q = 10, 1
    h = [1 , 2 , 4 ,2 , 8, 1, 2, 4, 8, 16] # output 3
    #    ^---- + ---^   0  ^--- + --^ + ^
    k = [3]
    l_k = max(k)



    distances = [99999999999] * N
    distances[N-1] = 0
    db = [ [0]*N for i in range(N)]

    for i in range(N-2, -1, -1):
        minLocalDistance = 99999999999
        for j in range(min(i+l_k, N-1), i, -1):   
            minLocalDistance = min(minLocalDistance, distances[j] + (h[i] <= h[j]))
            db[i][j] = distances[j] + (h[i] <= h[j])
            
        distances[i] = minLocalDistance
    print(f"Case #{testcase}: {distances[0]}")

注意：这与经典最小值不同。跳跃问题

Answer 1

考虑达到职位的最佳成本 i。它是以下较小的一个：

到达前面 k 个位置中的任何一个的最小成本加一（次优跳跃）；或
在同一 window（最佳跳跃）中到达任何较低高度位置的最低成本。

情况 (1) 可以使用滑动-window-最小算法来处理，您可以在此处找到描述，例如：。这需要每个位置的分摊常数时间，或者总共 O(N)。

案例 (2) 有一个有点明显的 BST 解决方案：随着 window 移动，将每个新位置插入按高度排序的 BST。删除 window 中不再存在的位置。此外，在每个节点中，将最小成本存储在其子树中。使用此结构，您可以在 O(log k) 时间内找到任何高度限制的最小成本。

情况 2 中的费用导致单个 k 值的总复杂度为 O(N log k)。这对于复杂性来说还算不错，但是这样的 BST 有点复杂并且通常不在标准库中提供。

你可以通过认识到如果 window 中的最小成本是 C，那么最优跳跃只有在它们来自成本 C 的前辈时才有用，因为成本 C+1 是可以通过次优跳跃实现。

然后，对于每个成本，您可以使用相同的滑动-window-最小值算法来跟踪 window 中的最小值高度对于具有该成本的节点。那么对于情况（2），你只需要检查最小成本的最小高度是否低于你想跳到的高度。

维护这些滑动 windows 每次操作再次需要分摊常数时间，导致整个单 k 值算法的时间为 O(N)。

我怀疑尝试同时管理多个 k 值是否有任何好处。

寻找增加元素值的最小跳跃次数

Finding minimum number of jumps increasing the value of the element

python

algorithm

dynamic-programming

优化一个 leetcode 风格的问题 - DP/DFS

我的尝试