動態規劃：概念

Question

真或假：

可以使用動態編程來解決任何問題，相對於它的輸入大小的多項式時間最壞情況下的時間複雜度。

是否有任何不是多項式的DP解決方案？

謝謝。

Answer 1

沒有爲Knapsack problem的量，最壞情況下的複雜度是O(Wn)W哪裏是揹包的容量和n是物品的數量的動態規劃算法。這種運行時間界限被稱爲僞多項式（作爲在實例中編碼的值發生）並且不能被視爲輸入大小中的多項式。所以，簡短的回答：錯誤。

此外，原來的問題是制定有點誤導，運行時複雜性是指特定的算法，而不是問題本身。

Answer 2

有很多。上面的例子是一個。另一個流行的例子是在O（n2^n）時間運行的旅行商問題的動態編程解決方案。請注意，Traveling Salesman的強力解決方案需要O（n！）時間，而動態編程解決方案則更好。