Достижение конца массива с последовательностью нечетных / четных переходов

Question

Я пытаюсь понять Python решение проблемы программирования, которая, кажется, использует динамическое c программирование. Я в состоянии следовать большинству решений, но я изо всех сил пытаюсь реально формализовать решение.

Проблема сформулирована следующим образом:

Вам дано целое число массив A. Из некоторого начального индекса вы можете сделать серию прыжков. (1-й, 3-й, 5-й, ...) прыжки в серии называются «нечетными» прыжками с номерами, а (2-й, 4-й, 6-й, ...) прыжки в серии называются прыжками с четными номерами.

Вы можете перейти вперед из индекса i в индекс j (с i < j) следующим образом:

• Во время нечетные пронумерованные прыжки (ie. прыжки 1, 3, 5, ...), вы переходите к индексу j, так что A[i] <= A[j] и A[j] является наименьшим возможное значение. Если таких индексов несколько j, вы можете перейти только к наименьшему из таких индексов j.

• Во время даже пронумерованных прыжков (ie. Прыжков 2, 4, 6, ...) вы переходите на индекс j, такой что A[i] >= A[j] и A[j] - это наибольшее возможное значение. Если существует несколько таких индексов j, вы можете перейти только к наименьшему такому индексу j.

• Возможно, что для некоторого индекса i являются недопустимыми прыжками.

Начальный индекс хороший , если, начиная с этого индекса, вы можете достичь конца массив, перепрыгивая несколько раз (возможно, 0 или более чем один раз).

Мы просим вас вернуть число хороших стартовых индексов.

Ниже в 1068 * показано решение этой проблемы, опубликованное несколькими авторами. Я понимаю, как он строит oddnext и evennext и что эти массивы технически содержат (местоположение индекса, на которое можно перейти с этого индекса с нечетным или четным переходом). Чего я не понимаю, так это как работает последний l oop и какова точная формулировка динамического программирования c.

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

Первая часть алгоритма идентифицирует для любого заданного индекса входного массива, к которому вы переходите с нечетным (oddNext) или четным (evenNext) прыжком. Некоторые индексы заполнены None, потому что вы не можете делать какие-либо легальные (четные или нечетные) прыжки с них.

Если у вас есть эта информация, чтобы ответить на ваш вопрос, обратите внимание на следующее:

• Любой индекс, который может законно перейти на хороший индекс , должен быть хороший индекс (вы можете «повторно использовать» решение для этого хорошего индекса, чтобы достичь конца)
• последний индекс входного массива всегда является «хорошим индексом» (т.е. вы конец уже достигнут)

В результате вы можете перейти назад от конца массива, чтобы определить хорошие индексы , проверив, будут ли они прыгать переслать в индекс, который вы уже определили как хороший (или не очень) индекс.

Обратите внимание, что это динамическое c программирование вычислений, поскольку вы устанавливаете периодические отношения между хорошими индексами и используете их как go в обратном направлении в массиве (то есть вы решение подзадач для динамического программирования c так называемым способом «снизу вверх» согласно их структуре зависимостей).

Следует отметить, что этот алгоритм вычисляет, хорош ли индекс для каждого местоположения и каждого возможного типа прыжка (т.е. мы полностью заполняем * Массивы 1036 * и even). Это связано с тем, что при выполнении итераций в динамических вычислениях c программирования различным начальным точкам массива может понадобиться , чтобы сделать нечетный или четный скачок из этого индекса, , даже если , когда начиная с из любого конкретного индекса, вы можете сделать это только с нечетным прыжком в соответствии с оператором задачи.

Отлично. В динамическом c программировании часто решают все подзадачи , даже если решение исходной проблемы не полагается на все из них. Обратите внимание, что это также , поэтому , в конце концов, вас интересует только то, какие индексы в массиве odd являются хорошими. Массив even был только частью динамического леса программирования c для заполнения массива odd.

Answer 2

каждую итерацию, которую вы проверяете, имеет ли этот индекс нечетный переход, если он это делает, проверяет пункт назначения перехода, если вы где-то в пункте назначения и имели четный переход, можете ли вы достичь конца, если это так, это значение индекса в нечетном должно быть истинным

затем вы проверяете то же самое для четного (есть ли у меня четный переход? Его dest - индекс с истинным в нечетном ?, установите четное значение true)

затем вы возвращаете количество нечетных истинных значений потому что ваш первый прыжок странный