動的計画法入門｜DPの基本概念と定番アルゴリズム問題まとめ

動的計画法（Dynamic Programming）とは

動的計画法（DP）は、代表的なアルゴリズム設計パラダイムのひとつです。この手法では、元の問題をいくつかの部分問題（サブプロブレム）に分割して解き、一度計算した部分問題の結果を記憶しておくことで、以降の計算に再利用します。同じ計算を繰り返さずに済むため、タスク全体の計算時間を大幅に削減できるのが大きな特徴です。

動的計画法を支える2つの重要な概念

動的計画法のテクニックには、主に次の2つの性質が関わっています。

• 部分重複問題（Overlapping Subproblem）：同じ部分問題が何度も現れる性質。メモ化などによって再計算を避けることができます。
• 最適部分構造（Optimal Substructure）：問題全体の最適解が、部分問題の最適解から組み立てられる性質。

このセクションで扱うトピック一覧

以下では、動的計画法を使って解ける定番のアルゴリズム問題を多数取り上げます。読みやすさのために、テーマごとに分類して紹介します。

基礎・古典的な問題

• フィボナッチ数列の生成
• n段目の階段に到達する方法の数（階段登り問題）
• 友人のペアリング問題
• アグリー数（Ugly Numbers）
• 1からnまでのすべての数の桁の合計を計算する
• N桁の数における非減少数の総数
• 桁の合計が指定した値になる数を見つける
• 数を3回分割して得られる最大の和
• 携帯電話の数字キーパッド問題

文字列・部分列に関する問題

• 最長共通部分列（Longest Common Subsequence）
• 最長増加部分列（Longest Increasing Subsequence）
• 最長ビトニック部分列
• 最大和増加部分列
• 最長回文部分列の長さ
• 最長回文部分文字列
• 編集距離（Edit Distance）
• 最短共通超系列（Shortest Common Super-Sequence）
• ワイルドカードによるパターンマッチング問題
• 回文分割アルゴリズム
• 連続する1を含まない2進文字列の数え方
• 指定した開始文字から始まる最長連続パス

配列・行列に関する問題

• 最大連続部分配列和（Largest Sum Contiguous Subarray）
• すべて1で構成される正方形部分行列の最大サイズ
• 行列内の長方形領域の最大和
• 行列内の最小コスト経路を求める
• 2回の走査でグリッド上の最大ポイントを収集する

コスト・経路の最適化問題

• 目的地までの最小コスト
• 目的地に到達するための最小トークン数
• 最小硬貨交換問題（Minimum Coin Change）
• 値に到達するために必要な最小完全平方数の和
• 可能なジャンプ回数の最小値
• フロイド・ワーシャル法（全点対間最短経路）
• 多角形三角分割の最小コスト
• ゲームで指定されたスコアに到達する方法の数

組合せ・その他の応用問題

• 箱積み問題（Box Stacking）
• 建物を建てる方法の数
• 4つのキーで入力できる最大の「A」の個数
• 最大独立集合問題（Largest Independent Set）
• ペアチェーンの最大長
• 株式を2回売買したときの最大利益
• 行列連鎖乗算（Matrix Chain Multiplication）
• 最適二分探索木のコスト
• ロッド切り出し問題（Rod Cutting）
• 部分和問題（Subset Sum）
• 等しい和に分割できるかの判定
• 頂点被覆問題
• 重み付きジョブスケジューリング問題
• ワードラップ問題
• 卵落としパズル