3.3. Динамическое программирование

Некоторые алгоритмы разбивают задачу на более мелкие подзадачи и используют решения подзадач, чтобы собрать решение для главной. Во время этого процесса количество подзадач может стать очень большим, и некоторые алгоритмы решают одну и ту же подзадачу многократно, что чрезмерно увеличивает время выполнения. Динамическое программирование упорядочивает вычисления и позволяет не вычислять уже известные значения повторно. Зачастую это экономит массу времени.

Задача со звонящим телефоном не подразумевает решения с помощью динамического программирования, поэтому мы рассмотрим другую. Представьте, что вместо ответа на звонок вы решаете поиграть в «Камни»: игру для двух игроков с двумя наборами камней по десять штук. С каждым ходом один игрок может взять один камень (из любого набора) или два камня (по одному из обоих). Когда камень забрали, он выходит из игры. Побеждает игрок, который заберет последний камень. Первый ход за вами.

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

Если игрок 1 может гарантированно выигрывать игру на , тогда мы будем говорить, что . Если у игрока 1 нет стратегии для выигрыша против игрока, который всегда делает правильные ходы, мы будем писать . Вычисление для произвольных и может звучать сложно, но мы воспользуемся результатами вычислений для меньших значений. Некоторые варианты игры, — в особенности , и , — явно приведут к победе игрока 1, так как игрок 1 может выиграть первым ходом. Таким образом, мы заполняем ячейки , и как . рис. (a)

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

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

Теперь мы можем заполнить . В случае игрок 1 может сделать три разных хода, которые приведут к ячейкам , и . Эти ячейки — выигрышные позиции для оппонента. Так, : см рис. рис. (d).

Мы можем продолжить заполнять , обращая внимание на то, что ячейка будет , если ячейки сверху, слева и слева по диагонали будут . Эти ячейки (, и ) соответствуют трем ходам, которые может сделать игрок 1. См. рис. рис. (e)

Алгоритм Rocks определяет, выиграет игрок 1 или нет. Если игрок 1 выигрывает , то Rocks выдаст . Если игрок 1 проигрывает, то Rocks выдаст . Мы ввели искусственное начальное условие, , чтобы упростить псевдокод.

Rocks(n, m):
    R(0,0) = L
    for i from 1 to n:
        if R(i-1,0) = W:
            R(i,0) = L
        else:
            R(i,0) = W
    for j from 1 to m:
        if R(0,j-1) = W:
            R(0,j) = L
        else:
            R(0,j) = W
    for i from 1 to n:
        for j from 1 to m:
            if R(i-1,j-1)=W and R(i,j-1)=W and R(i-1,j)=W:
                R(i,j) = L
            else:
                R(i,j) = W
    return R(n,m)

Более быстрый алгоритм для решения этой головоломки опирается на простую закономерность в и проверяет, чётные и или нет. Если оба числа чётные, то игрок проигрывает (см. таблицу выше).

FastRocks(n, m):
    if n % 2== 0 and m % 2 == 0: // оба числа чётные
        return L
    else:
        return W

Тем не менее, хотя FastRocks и эффективнее, чем Rocks, изменить его для схожих вариантов игры может быть сложно. Например, вариант, в котором игрок может убирать до трёх камней из наборов. Перед нами пример того, как более медленный алгоритм может быть полезнее, чем быстрый.