使用動態規劃解決問題的資格

Question

對於使用dp解決的問題，我們是否需要最優子結構和重疊子問題都可以由問題滿足，或者任何一個條件都有資格使用dp技術來解決問題？

如果問題P1具有最佳子結構但子問題不重疊，並且如果P2具有重疊的子結構但最佳子結構不滿足，我仍然可以使用dp解決P1和P2嗎？

Answer 1

這取決於一個問題，但它似乎P1和P2都是動態編程匹配很差：

• P1 - 您可以使用DP，但你不會得到任何性能提升，因爲問題不重疊，您不能重用解決方案。
• P2 - 如果沒有最佳的子結構，那麼有一個子問題的解決方案，你沒有幫助找到解決更大的問題的解決方案。