Тимус: задача 1501 - Динамика
19 февраля 2024
Задача
Решение не динамика
Подсказка говорит, что задача на динамику. Однако первое мое решение было не совсем верным. Сначала я пытался построить путь выбирая одну из карт. Если путь не получался, то возвращался назад и брал другой вариант, запоминая выбранную карту. Карты обозначил как -1 и +1, соответственно сумма не должна была превышать по модулю 1. Такое решение не проходит по времени, так как цепочки постоянно пересчитываются если надо возвращаться много раз. Сложность такого решения o(2**n)
Решение динамика
На этапе чтения надо посчитать суммы для каждой позиции в исходной колоде. Имя скажем, позицию i, j сложив sum[i] и sum[j], мы можем узнать можно ли попасть в такую позицию или нет. Теперь для позиции i = n, j = n надо проверить, можно ли туда попасть сверху или сбоку (имеется в виду [i-1][j] и [i][j-1]). Напрашивается рекурсия. Если получается так дойти до начала, то решение есть. Сложность такого решение o(n**2).