动态规划:概念

Question

真或假：

任何可以用动态规划解决的问题，其输入大小都具有多项式时间、最坏的时间复杂度。

有什么不是多项式的DP解吗？

谢谢。

Answer 1

对于背包问题有一个动态规划算法，最坏的情况是O(Wn)，其中W是背包的容量，n是条目的数量。这种运行时界被称为伪多项式(作为在实例中编码的值)，在输入大小上不能视为多项式。所以，简短的回答:假的。

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

Answer 2

有很多。上面的例子就是一个。另一个流行的例子是在O(n2^n)时间内运行的旅行推销员问题的动态规划解。注意，旅行推销员的蛮力解取O(n!)时间，与之相比，动态规划解决方案更好。