Короткий ответ - нет.Динамическое программирование - это скорее стратегия повышения производительности / сокращения сложности времени выполнения, чем фактический алгоритм.Не зная фактического алгоритма для конкретной задачи, невозможно что-либо сказать о сложности времени.
Идея DP состоит в том, чтобы использовать запоминание (занимая некоторое пространство) для ускорения существующего алгоритма.Более того, каждый алгоритм, к которому вы можете применить DP, может ускоряться разными способами.Без повторного вычисления одной и той же подзадачи вам придется сохранять промежуточные результаты в другой структуре данных.Если результат снова понадобится в вашей структуре данных, вы напрямую вернете промежуточные результаты, которые вы сохранили
С учетом сказанного, временная сложность проблем DP - это число уникальных состояний / подзадач * время, затрачиваемое наstate.
Вот один пример, когда DP решает N подзадач и вычисление не является Ω (N).давайте предположим, что ваш DP требует O (n) подзадач, а оценка каждой подзадачи требует O (logn) двоичного поиска плюс операции с постоянным временем.
Тогда общий алгоритм будет принимать O (n * logn).