可以將每個迭代算法轉化爲動態規劃嗎？

Question

已經有很多討論，每個遞歸算法都可以轉化爲迭代算法..

但是...每個迭代算法都可以轉化爲動態規劃嗎？

我開始學習動態規劃......並且我遇到了很多問題..即使我可以找到遞歸解決方案，並且我擅長將它們轉化爲迭代算法，但我仍然可以'將這些迭代算法轉化爲動態編程......當然，確實知道每個迭代算法都可以轉化爲動態...

Answer 1

我希望通過動態編程，您的意思是the same thing as Wikipedia does - 是將算法分解成更小的子問題的算法，並且使用記憶來避免必須兩次解決相同的問題。

動態規劃不能有效地應用於所有迭代算法。對於動態規劃是有用的，這個問題需要兩個屬性：

1. 重疊的子問題 - 遞歸解決問題的時候，你需要遇到相同的子問題，使用相同的參數，超過一次，否則memoizing是一種浪費的時間和記憶。
2. 最佳子結構 - 知道如果你有子問題的解決方案，整個問題的解決方案很容易計算。