動的プログラミングによる解決の適性

Question

dpを使用して解くべき問題については、最適な基礎構造と重複する部分問題の両方が問題に満たされる必要がありますか、またはいずれかの条件によってdp技法を使用して解くことができますか？

問題P1が最適な部分構造を持っていて、部分問題が重複していない場合、部分構造が重複していて最適部分構造が満たされていない場合、dpを使ってP1とP2を解決できますか？

Answer 1

それは問題に依存しますが、P1とP2の両方が、動的プログラミングの貧一致しているようだ：

• P1 - あなたはDPを使用できますが、任意のパフォーマンスの向上を得ることはありません、ので、問題は重複しておらず、ソリューションを再利用することはできません。
• P2 - 最適な部分構造がない場合、部分問題の解を持つことは、より大きな問題の解を見つけるのに役立ちません。