动态规划：概念

Question

真或假：

可以使用动态编程来解决任何问题，相对于它的输入大小的多项式时间最坏情况下的时间复杂度。

是否有任何不是多项式的DP解决方案？

谢谢。

Answer 1

没有为Knapsack problem的量，最坏情况下的复杂度是O(Wn)W哪里是背包的容量和n是物品的数量的动态规划算法。这种运行时间界限被称为伪多项式（作为在实例中编码的值发生）并且不能被视为输入大小中的多项式。所以，简短的回答：错误。

此外，原来的问题是制定有点误导，运行时复杂性是指特定的算法，而不是问题本身。

Answer 2

有很多。上面的例子是一个。另一个流行的例子是在O（n2^n）时间运行的旅行商问题的动态编程解决方案。请注意，Traveling Salesman的强力解决方案需要O（n！）时间，而动态编程解决方案则更好。