分割統治と動的計画法の主な違いは、分割統治が小問題の解を組み合わせて主問題の解を求めるのに対し、動的計画法は小問題の結果を用いて主問題の最適解を求める点です。
分割統治法と動的計画法は、問題を解くための2つのアルゴリズムまたはアプローチです。
分割統治アルゴリズムでは、問題を小問題に分割し、その解を組み合わせて元の問題の解を求める。
しかし、動的計画法では、小問題を個別に解くことはしない。
しかし、動的計画法では、部分問題を個別に解くのではなく、部分問題の解答を保存しておき、類似の問題でそれを利用する。
分割統治とは？
分割統治とは、主問題を小さな副問題に分割することである。
小問題は何度も何度も分割される。
ある時点で，これ以上分割できない段階が来る． そのとき、それぞれの問題を独立に解くことができる。
最後に、すべての小問題の解を組み合わせて、本問題の解を得ることができる。
分割統治には3つの主要なステップがあります。
それらは次の通りです。
分割する（Break）- 主問題をサブ問題の集まりに分割する。
解く（Conquer） – 各サブ問題を個別に解く
結合（Merge） – 主問題の解を得るために、サブ問題の解を結合する。
動的計画法とは
動的計画法は，主問題をより小さな部分問題に分割するが，部分問題を独立に解くことはしない． 小問題の結果を記憶しておき，類似の小問題を解くときに利用するのである．小問題の結果を記憶することを暗記という。
現在の部分問題を解く前に，以前の部分問題の結果をチェックする．最後に、すべての部分問題の結果を確認し、最適解を求める。
この方法は、何度も答えを計算する必要がないため、効果的である。
通常、最適化には動的計画法が使用される。
動的計画法の構成要素は以下の通りです。
単純な部分問題 – 元の問題を類似した構造を持つ小さな部分問題に分割する。
問題の最適な部分構造 – 主問題の最適解はその部分問題の最適解の中にある
重複する部分問題 – 同じ部分問題を何度も解く状況
ディバイド＆コンカーとダイナミックプログラミングの違い
定義
Divide and conquer は、問題を直接解けるほど単純になるまで、同じ型または関連する型の 2 つ以上の部分問題に再帰的に分解するアルゴリズムです。
しかし、動的計画法は、重複する部分問題と最適部分構造の性質を持つ問題のクラスを効率的に解くのに役立つアルゴリズムです。
タイプ
分割統治法と動的計画法の主な違いは、分割統治法が再帰的であるのに対し、動的計画法は非再帰的であることである。
サブ問題
分割統治法では，部分問題は互いに独立である．しかし、動的計画法では、小問題は相互に依存する。
これが分割統治と動的計画法のもう一つの大きな違いです。
消費時間
分割統治と動的計画法のもう一つの違いは、時間消費です。
分割統治法は、各サブプロブレムを独立に解決する。
そのため、より時間がかかる。
一方、動的計画法は、前の小問題の解答を利用する。
そのため、時間がかからない。
効率性
効率性についても、分割統治と動的計画法の違いがあります。
動的計画法は分割統治法より効率的です。
アプリケーション
マージソート、クイックソート、バイナリサーチは分割統治を、行列の連鎖積算と最適二分探索木は動的計画法を用いている。
結論
分割統治法と動的計画法の主な違いは、分割統治法が部分問題の解を組み合わせて主問題の解を求めるのに対し、動的計画法は部分問題の結果を用いて主問題の最適解を求めるという点です。
