27

動的計画法を使用して解決できる多くの問題があります。たとえば、最長増加部分列です。この問題は、2つのアプローチを使用して解決できます

  1. メモ化（トップダウン）-再帰を使用してサブ問題を解決し、結果をハッシュテーブルに保存します。
  2. 集計（下から上）-反復アプローチを使用して、最初に小さなサブ問題を解決し、次に大きな問題の実行中にそれを使用することによって問題を解決します。

私の質問は、時間と空間の複雑さの観点からどちらがより良いアプローチですか？

4

4 に答える 4

41

簡単な答え：それは問題によって異なります！

メモ化は通常、より多くのコードを必要とし、それほど単純ではありませんが、いくつかの問題、主に答えに到達するために行列全体のすべての値を計算する必要がない問題では、計算上の利点があります。

集計はより簡単ですが、不要な値を計算する場合があります。ただし、すべての値を計算する必要がある場合は、オーバーヘッドが小さいため、通常、この方法の方が高速です。

于 2012-08-20T18:15:59.020 に答える
1

漸近的に、トップダウンの動的計画法の実装は、同じ漸化式を使用していると仮定すると、ボトムアップの実装と同じです。ただし、メモ化で使用される再帰のオーバーヘッドのため、ボトムアップの方が一般的に効率的です。

于 2012-08-20T18:10:04.817 に答える
1

まず、動的計画法とは何かを理解しますか？ 手元の問題をサブ問題に分解でき、その解決策も最適であり、元の/より大きな問題の解決策に到達するために組み合わせることができる場合。このような問題には、動的計画法を適用できます。これは、サブ問題の結果をプログラムメモリに保存し、後の段階で再計算するのではなく再利用することで問題を解決する方法です。

動的計画法を使用する理想的なケースは、サブ問題の解決策を複数回再利用できる場合です。そうでない場合、結果を保存しても意味がありません。

これで、動的計画法をボトムアップアプローチ（集計）とトップダウンアプローチ（メモ化）に適用できます。

集計：最小のサブ問題の解を計算することから始め、一度に1レベル上に進みます。基本的にボトムアップアプローチに従います。ここで、サブ問題のそれぞれについて、将来本当に必要かどうかを知らずに、徹底的に解決策を見つけていることに注意してください。

メモ化：元の問題から始めて、解決策がわかっているベースケースまで1レベル下に分解し続けます。ほとんどの場合、このような分解（トップダウンアプローチ）は再帰的です。したがって、再帰呼び出しのために問題が各ステップのサブソリューションを使用している場合、かかる時間は遅くなります。ただし、すべてのサブソリューションが必要ない場合は、メモ化の方が集計よりもパフォーマンスが高くなります。

この短いビデオは非常に役に立ちました：https ：//youtu.be/p4VRynhZYIE

于 2021-09-25T02:58:10.150 に答える
-5

問題にoverlapping sub-problemsプロパティがある場合はを使用しMemoization、そうでない場合は問題によって異なります

于 2012-08-20T19:57:38.863 に答える