動的計画法の基本


難易度 簡単に
よく聞かれる インフォシス MAQ
動的計画法 理論

動的計画法の基本では、DPの基本と、貪欲法である分割統治法との違いについて説明します。

動的計画法は、再帰と分割統治のようなアプローチです。 問題をサブ問題に分割します。 ただし、分割統治法や再帰法のようにこれらのサブ問題を個別に解決する代わりに、重複問題としても知られる同様の計算に以前のサブ問題の結果を使用します。

プログラムの最適化に使用されます。 以前に計算された結果を使用するため、その指数関数的な時間計算量を使用すると、多項式に減らすことができます。 たとえば、醜い数の再帰的解の時間計算量は指数関数的であり、DP解の時間計算量は線形です。

DPのいくつかの基本的な問題

  • 醜い数字の問題
  • コイン交換
  • フィボナッチ数
  • ベル数の問題
  • ハノイの塔
  • ベル番号
  • ナップザック問題

動的計画法(DP)と欲張り法

DPでは、各ステップで現在のソリューションと以前のソリューションを考慮してソリューションを評価し、最適なソリューションを取得します。 ただし、欲張りアルゴリズムでは、現在の状況のみを考慮して最適なオプションを選択します。

欲張り法は一般にDPよりも高速であり、将来の使用のために以前に計算された値を保存しないためメモリ効率も高くなりますが、最適なソリューションを保証するものではありません。

動的計画法(DP)と分割統治法

分割統治では、問題をサブ問題に分割し、各サブ問題を個別に解決します。 ただし、DPでは、問題を個別に解決するのではなく、以前に取得した結果を新しい計算に使用します。 言い換えれば、分割統治+メモ化=トップダウンの動的アプローチと言えます。

(メモ化とは、以前に計算された結果を一般にハッシュマップに保存して、同じ問題が何度も計算されないようにする手法を指します。)

動的計画法(DP)vs再帰法

DPは、以前に計算されたソリューションを保存して、再計算を回避するために、将来必要になったときにそれらを使用します。 ただし、再帰的には、値を格納しないため、再計算が不要になる可能性があります。

再帰は問題の再計算に数回つながるため、そのような場合、再帰の時間計算量は常にDPソリューションよりも大きくなります。

この記事では、 動的計画法 基本。 次の記事では、DPに関するいくつかの基本的な問題について説明します。

参照 面接の質問