動的計画法

スカラー乗算の数を最小化するために行列の連鎖を括弧でくくる最適な方法を見つけます。CLRSの第15章の古典的な動的計画法の問題です。

動的計画法を使用して冗長な計算を避けながらフィボナッチ数を効率的に計算します。メモ化の力を示し、指数時間の再帰的解を線形時間アルゴリズムに変換します。動的計画法の概念への古典的な入門です。

2つの列に同じ順序で存在する最長の部分列を見つけます。動的計画法を使用して解テーブルを構築します。DNA配列アライメント、ファイル差分ツール（diff）、盗作検出などの応用があります。

1つの文字列を別の文字列に変換するために必要な単一文字編集（挿入、削除、置換）の最小数を計算する動的計画法アルゴリズムです。スペルチェック、DNA配列アライメント、自然言語処理の基礎です。

与えられた重さと価値を持つアイテムを選択し、重量制限内で総価値を最大化する古典的な動的計画法の問題です。各アイテムは一度だけ取ることができます（0/1）。リソース配分、ポートフォリオ最適化、貨物積載に応用されます。

すべての要素が昇順である最長の部分列を見つけます。古典的な動的計画法の問題です。

O(n)時間で最大の合計を持つ連続部分配列を見つけるエレガントな動的計画法アルゴリズムです。各ステップで現在の部分配列を拡張するか新しいものを開始するかを決定することで、貪欲法とDPの原則を組み合わせます。株式利益の最適化、信号処理、DP最適化技術の理解に不可欠です。

目標金額を作るために必要な最小のコイン数を見つける古典的な動的計画法の問題です。解がより小さい金額の解に依存する最適部分構造を示します。金融システム、自動販売機、リソース配分の最適化で広く適用されています。

文字列を回文部分文字列に分割するために必要な最小カット数を見つける動的計画法の問題です。DPを使用してどの部分文字列が回文かを事前計算し、最適なカットを見つけます。テキストセグメンテーション、DNA配列分析、文字列最適化問題に応用されます。