algorithm - 动态规划 : Concept

Question

判断对错:

Any problem that can be solved using dynamic programming has a polynomial time worst case time complexity with respect to its input size.

有没有不是多项式的DP解？

谢谢。

Answer 1

Knapsack problem 有一个动态规划算法最坏情况下的复杂度为 O(Wn)，其中 W 是背包的容量，n 是元素的数量。这样的运行时边界被称为伪多项式(因为在实例中编码的值出现)并且不能被视为输入大小的多项式。所以，简短的回答:错误。

此外，原始问题的表述有点误导；运行时复杂度指的是特定算法，而不是问题本身。