Что ж, раз кошачьего вытащили из мешка, самое время отметить, что описанные здесь методы применимы очень широко. Это отличная задача по своему построению именно благодаря прогрессивному решению.
Во-первых, рекурсивное решение. Следующее запоминание / ДП сверху вниз. Устранение мемо-таблицы за счет инверсии графа зависимостей, также известного как DP снизу вверх.
Но отношение, на которое я хочу обратить внимание, заключается в следующем: если вектор состояния восходящего решения DP представляет собой линейную комбинацию предыдущих элементов, то преобразование может быть, как показано здесь, представлено в виде матричного возведения в степень.
Вы сразу перешли к подходу «разделяй и властвуй», который я приветствую, хотя кандидаты, более поверхностно знакомые с линейной алгеброй, могут заметить, что возведение в степень можно выполнить с помощью разложения по собственным значениям.
Это дает линейное (операции для каждого элемента по диагонали), а не логарифмическое время, но такое же быстрое возведение в степень повторным возведением в квадрат можно выполнить для элементов самой диагонали.
Возможно, это ненужное отступление, но я ценю полноту, которую это обеспечивает в путешествии от алгоритмического проектирования к линейному анализу и численным методам, и, кроме того, то, что его можно обобщить на любую такую задачу ДП, удовлетворяющую упомянутому линейному условию.
