グリーディ法とダイナミックプログラミングの大きな違いは、グリーディ法が行う決定（選択）はこれまでの決定（選択）に依存し、将来の選択や部分問題のすべての解には依存しないことです。
一方、動的計画法では、前段階のすべての決定に基づいて決定を行い、問題を解決する。
アルゴリズムとは、問題を解決するための体系的な手順のことである。
貪欲法と動的計画法は2つのアルゴリズムです。
どちらも最適化問題を解くのに使われます。
グリーディメソッドとは
貪欲法とは、複数の現在価値の中から最適な選択肢を見つけ出す方法です。
この方法では、最初の段階を考慮し、将来の出力を考慮せずに出力を決定する。
つまり、その時点での最適な選択肢を考えることで問題を解決するのがグリーディ法です。
貪欲アルゴリズムは、問題が貪欲選択性と最適部分構造という2つの性質を含んでいる場合に機能する。
局所最適解を作ることで、全体最適解を求めることができる。
つまり、貪欲な選択をすることで、最適解を見つけることができるのです。
したがって、この性質は貪欲選択性と呼ばれる。
さらに、最適解は最適部分解を含む。
従って、この性質を最適部分構造と呼ぶ。
動的計画法とは
動的計画法では，主問題を小さな小問題に分割する．そして，小問題の解答を記憶しておき，類似の小問題に適用していく方法である．ここで、小問題の答えを記憶することを暗記という。
そして、小問題の解答をチェックし、最終的に最適解を導き出すのです。
動的計画法は、過去の解答を確認し、同じ解答を何度も計算することを避けるため、より効率的です。
動的計画法では、主問題の最適解は、その下位問題の最適解の中にある。
また、同じ部分問題に何度も直面する状況を部分問題の重複と呼ぶ。
欲張りな方法と動的計画法の違い
定義
貪欲法とは、大域的な最適値を求めることを目的として、各店舗で局所的に最適な選択を行うという問題解決のヒューリスティックに従うアルゴリズムです。
一方、動的計画法は、重複する部分問題と最適部分構造の性質を持つ問題のクラスを効率的に解くことを支援するアルゴリズムです。
これらの定義により、グリーディ法とダイナミックプログラミングの主な違いを説明することができる。
効率性
さらに、Greedy Method と Dynamic Programming の大きな違いは、その効率性です。
Greedy 法は効率が悪く、Dynamic Programming は効率が良い。
プロセス
さらに、グリーディ法とダイナミックプログラミングの重要な違いは、グリーディ法はまずその時点で最適と思われる選択を行い、その結果得られる部分問題を解くという点です。
動的計画法では、すべての部分問題を解いてから、最適解を求めるのに役立つものを選択する。
意思決定
Greedy 法と Dynamic Programming のもう一つの違いは、意思決定の方法です。
Greedy 法は最初の段階を考慮して決定を行うが、Dynamic Programming はすべての段階で決定を行う。
結論
Greedy 法による決定（選択）は、これまでの決定（選択）に依存し、将来の選択や部分問題の全解に依存しない。
しかし、動的計画法では、前段階のすべての決定に基づいて決定を行い、問題を解決していく。
これがグリーディ法とダイナミックプログラミングの大きな違いです。
