ボトムアップがトップダウンよりも有益である動的プログラミングの問題文をいくつか教えてください。(つまり、単純な DP はより自然に機能しますが、メモ化は実装が難しいでしょうか?)
私は、メモ化による再帰の方がはるかに簡単であり、ボトムアップがより良い/おそらく唯一の実行可能なアプローチである問題を解決したいと考えています。
理論的にはどちらも同等であることを理解しているため、実装の容易さのようなものでも利点としてカウントされます.
4050 次
2 に答える
7
手元の問題に応じて、メモ化によるボトムアップまたはメモ化によるトップダウン再帰を適用します。
たとえば、パス グラフの最小重みに依存しないパスを見つける必要がある場合は、可能なすべての下位問題を解決する必要があるため、ボトムアップ アプローチを使用します。
しかし、ナップザック問題を解決する必要がある場合は、限られた数のサブ問題を解決する必要があるため、再帰的なトップダウンとメモ化を使用することをお勧めします。ナップザック問題にボトムアップでアプローチすると、アルゴは元のサブ問題では使用されない多くの冗長な問題を解決します。
于 2013-01-13T06:30:13.907 に答える