以奇偶跳转序列到达数组末尾

Question

我试图理解一个Python解决方案，它似乎使用了动态编程。我能够遵循大部分解决方案，但我正在努力使解决方案真正正规化。

问题陈述如下：

您将获得一个整数数组A。从某个起始索引，您可以进行一系列跳转。（第一、第三、第五……）序列中的跳转称为“奇数”编号跳转，以及（第2、第4、第6、…）序列中的跳转称为偶数跳转。

你可以从indexi跳转到index j（withi

>

在偶数跳转（即跳转2, 4, 6, ...)，你跳转到索引j使得A[i]

可能的情况是，对于某些索引i没有合法的跳转。

如果从该索引开始，您可以通过跳几次（可能是0次或多次）到达数组的末尾，则起始索引是好的

我们要求您返回良好的起始索引数。

下面我展示了一些作者已经发布的Python解决方案。我了解它是如何构建oddnext和evennext的，以及这些数组在技术上所包含的内容（通过奇数或偶数跳转从该索引跳转到的索引位置）。我不明白的是最后一个循环是如何工作的，以及它背后的精确动态规划公式是什么。

def odd_even_jumps(self, A):
    N = len(A)

    def make(B):
        ans = [None] * N
        stack = []  # invariant: stack is decreasing
        for i in B:
            while stack and i > stack[-1]:
                ans[stack.pop()] = i
            stack.append(i)
        return ans

    B = sorted(range(N), key = lambda i: A[i])
    oddnext = make(B)
    B.sort(key = lambda i: -A[i])
    evennext = make(B)

    odd = [False] * N
    even = [False] * N
    odd[N-1] = even[N-1] = True

    # Why does this loop start from the end? 

    for i in range(N-2, -1, -1):
        if oddnext[i] is not None:
            odd[i] = even[oddnext[i]]
        if evennext[i] is not None:
            even[i] = odd[evennext[i]]

    return sum(odd)




Answer 1

每次迭代，你检查这个索引是否有一个奇数跳跃，如果它检查跳跃目的地，如果你在目的地的位置，并且有一个偶数跳跃，你能到达终点吗，如果是这样，这个奇数索引值应该是真的

然后检查相同的偶数（我有偶数跳转吗？它的dest是索引，在奇数中为true？，将偶数值设置为true）

然后返回奇数个真值，因为第一次跳转是奇数

Answer 2

算法的第一部分识别输入数组的任何给定索引，使用奇数（oddNext）或偶数（evenNext）跳转可以跳转到哪里。某些索引填充有None，因为您不能从它们进行任何合法（偶数或奇数）跳转。

获得此信息后，要回答您的问题，请注意以下几点：

• 任何可以合法跳转到好索引的索引都必须是一个好索引（你可以“重新使用”那个好索引的解决方案以达到最后）
• 输入数组的最后一个索引总是一个好索引（即你已经到达了终点）

因此，您可以从数组的末尾向后移动，通过检查它们是否会跳转到您已经确定为好（或不好）索引的索引来识别好的索引。

请注意，这是一个动态编程计算，因为您正在建立良好索引之间的循环关系，并在数组中向后移动时利用它（也就是说，您正在以所谓的“自下而上”的方式解决动态编程子问题，根据它们的依赖性结构）。

需要注意的一点是，该算法计算每个位置和每个可能的跳转类型的索引是否良好（即我们完全填充奇数和偶数数组）。这是因为，当您在动态编程计算中迭代时，数组的不同起点可能需要从该索引进行奇数或偶数跳跃，即使从任何特定索引开始时，您只能根据问题陈述。

那很好。在动态规划中，一个人通常会解决所有的子问题，即使原始问题的解决方案并不依赖于所有子问题。请注意，这也是为什么最后您只关心odd数组中的哪些索引是好索引的原因。偶数数组只是填充奇数数组的动态编程框架的一部分。