動的計画法と分割統治法の違い、その適用方向と問題例（1）：棒鋼切断

Difference Between Dynamic Programming

1.動的計画と分割統治法の違い：
は再帰を使用しますが、分割統治法のサブ問題は繰り返されず、動的ルールのサブ問題が繰り返されるため、再計算を回避するためにサブ問題の解をテーブルに保存する必要があります。 。

2.動的計画法の適用方向（この方法で解決できる問題の特徴）：

動的計画法は、最適化問題を解決するために使用されます。いつ '・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・············ '問題の商に、動的計画法を使用して問題を解決すると考えることができます]

3.動的計画手法の導入：
動的計画は、時間を節約するために追加のメモリを支払うことです。これは、典型的な時空間バランスです。
3.1。動的計画法アルゴリズムの設計手順：

最適な下部構造：問題の最適な解決策は、関連するサブ問題の最適な解決策の組み合わせであり、これらのサブ問題は独立して解決できます。

3.2。動的計画法アルゴリズムの実現方法：
a）メモ付きのトップダウン方式：
通常の再帰的プロセスに従って記述されますが、プロセス内の各サブ問題を保存します。サブ問題を解決するときは、最初にこのソリューションが保存されているかどうかを確認し、保存されている場合は戻ります。保存されていない場合は、保存して計算後に返します。
鉄筋切断の擬似コード：

b）ボトムアップ方式：
最初に最小のサブ問題の解を解き、次に問題が徐々に拡大します。解決する問題に拡大すると、すべての前提条件のサブ問題が解決されます（サブ問題はスケールに従ってソートされ、解は小さいものから大）。
頻繁な再帰呼び出しのオーバーヘッドがないため、ボトムアップ方式時間計算量の係数は小さくなります。
鉄筋切断の擬似コード：

2層サイクル： ループの1つの層は、小さな問題をトラバースするために使用されます->大きな問題2番目の層は、この小さな問題を解決するために使用されます。

c）完全なコード：最適解の値rと最適解sを返します。


参考資料： アルゴリズム入門ページ359、第15章動的計画法

1.動的計画法は時間に空間を使用します。サブ問題の繰り返し計算を回避するために、サブ問題の解を保存するための配列を開発する必要があります。
2.動的計画法は、最適化問題、一般的に使用されるボトムアップ法を解決するために使用されます（最初にサブ問題を解決し、次に徐々に拡大します。小さな問題から大きな問題まで、ループトラバーサルによく使用されます）。