動的計画法(英語:Dynamic programming、略称 DP)は、数学、経営科学、計算機科学、経済学、バイオインフォマティクスなどで使用される、元の問題を比較的単純な部分問題に分解することで複雑な問題を解く方法です。
想像してみてください。あなたは今、
n段の階段を上っています。毎回あなたは1段または2段の階段を上がれます。では、頂上に到達する方法は全部で何通りあるでしょうか?
もし最上階の目標(第
n段)から考え始めると、複雑に感じるかもしれません。しかし、考え方を変えてみましょう:第
n段の階段に到達するには、第n-1段から1歩で上がるか、または第n-2段から2歩で上がるしかありません。したがって、第n段に到達する方法の数は、第n-1段に到達する方法の数に、第n-2段に到達する方法の数を足したものに等しくなります。
このような大きな問題を複数の重複する部分問題に分解し、部分問題の解を保存することで重複計算を避け、元の問題を効率的に解決するという方法が、動的計画法(Dynamic Programming、略称 DP)です。
中心となる考え方
動的計画法の核心は、計算済みの解を記憶することです。 。
動的計画法は通常、以下の性質を持つ問題を解決するために使われます:
- 重複する部分問題:再帰的な求解の過程で、同じ部分問題が何度も計算されること。
- 最適部分構造:ある問題の最適解が、その部分問題の最適解を含んでいること。
簡単なフローチャートを使って、動的計画法の問題解決の考え方を理解しましょう:
上の図は、動的計画法の問題を解く典型的な手順を示しています:問題の定義から始め、分析によって部分問題の構造を見つけ、状態と状態遷移方程式で形式化し、最後に明確な初期条件と計算順序によって答えを得ます。
再帰から動的計画法へ:階段を上る問題
定番の「階段を上る」問題を用いて、再帰から動的計画法への最適化の過程を体験しましょう。
問題の説明
あなたが階段を上っているとします。n段上がると頂上に到達できます。毎回あなたは1 或 2段の階段を上がれます。頂上まで到達する方法は何通りあるでしょうか?
方法1:ブルートフォース再帰(非効率)
冒頭の分析に基づき、再帰式を直接書くことができます:f(n) = f(n-1) + f(n-2)ここで、f(1) = 1, f(2) = 2。
例
"""递归解法"""
if n == 1:
return 1
if n == 2:
return 2
return climb_stairs_recursive(n - 1) + climb_stairs_recursive(n - 2)
# 测试
print(f"5 段目までの階段の登り方の数(再帰): {climb_stairs_recursive(5)}") # 输出: 8
欠点の分析:この再帰には大量の重複計算が存在します。例えば、f(5)を計算するにはf(4)とf(3)が必要で、f(4)を計算するにはf(3)とf(2)も必要です。ここでのf(3)は2回計算されてしまいます。nが大きくなると、時間計算量は指数関数的なO(2^n)となり、効率が非常に低くなります。
方法2:メモ化を備えた再帰(トップダウン)
配列(「メモ」)を使って計算済みの結果を保存し、重複計算を避けることができます。
例
"""メモ化再帰(トップダウン)"""
# 初始化备忘录,-1 表示未计算
memo = [-1] * (n + 1)
def helper(x: int) -> int:
# 基础情况
if x == 1:
return 1
if x == 2:
return 2
# 如果已经计算过,直接返回结果
if memo[x] != -1:
return memo[x]
# 否则,计算并存入备忘录
memo[x] = helper(x - 1) + helper(x - 2)
return memo[x]
return helper(n)
print(f5段目までの登り方の数(メモ化): {climb_stairs_memo(5)}) # 输出: 8
この方法の時間計算量はO(n)まで低下します。各部分問題は1回だけ計算されるためです。空間計算量はO(n)です。これはすでに一種の動的計画法の考え方であり、「トップダウン」 或 「メモ化探索」。
方法3:漸化式配列(ボトムアップ、標準DP)
最小の部分問題から直接始めて、元の問題まで段階的に漸化式で進めます。通常は配列dpを使って状態を保存します。
例
"""动态规划(自底向上)"""
if n <= 2:
return n
# 1. 状態配列を定義する:dp[i] は第 i 段の階段に登る方法の数を表す
dp = [0] * (n + 1)
# 2. 确定初始条件
dp[1] = 1
dp[2] = 2
# 3. 状态转移:根据状态转移方程递推
for i in range(3, n + 1):
dp[i] = dp[i - 1] + dp[i - 2]
# 4. 返回最终结果
return dp[n]
print(f5段目に登る方法の数(DP): {climb_stairs_dp(5)}) # 输出: 8
方法4:空間最適化(ローリング配列)
状態遷移方程式を観察するとdp[i] = dp[i-1] + dp[i-2]、現在の状態は直前の2つの状態だけに依存することがわかります。したがって、配列全体を保存する必要はなく、dp2つの変数だけでローリング更新すれば十分です。
例
"""动态规划(空间优化版)"""
if n <= 2:
return n
# 2つの変数だけを使って dp[i-1] と dp[i-2] を表す
prev, curr = 1, 2 # dp に対応
for i in range(3, n + 1):
# 计算新しい当前值
new_curr = prev + curr
# 変数をローリング更新し、次のループに備える
prev, curr = curr, new_curr
return curr
print(f5 段目まで登る方法の数(最適化DP): {climb_stairs_optimized(5)}) # 输出: 8
最適化後、空間計算量はO(n)に低下しました。O(1)。
動的計画法の問題解決フレームワーク
階段を上る問題を通して、動的計画法を解くための汎用的な4つのステップをまとめることができます:
ステップ1: 状態を定義する
1つまたは複数の配列(通常dpと呼ばれる)で部分問題の解を表します。重要なのは、dp[i]またはdp[i][j]が何を意味するのかを明確にすることです。
階段を上る問題では、
dp[i]を「第i段の階段に到達する方法の総数」と定義します。
ステップ2: 状態遷移方程式を決定する
を見つけます。dp[i]と前の状態(例:dp[i-1], dp[i-2])との間の関係です。これは動的計画法の核心であり難所です。
階段を上る問題では、状態遷移方程式は次のとおりです:
dp[i] = dp[i-1] + dp[i-2]。
ステップ3: 初期条件(ベースケース)を決定する
最小の、これ以上分割できない部分問題の解です。これは漸化式の出発点であり、手動で定義する必要があります。
階段を上る問題では、初期条件は次のとおりです:
dp[1] = 1,dp[2] = 2。
ステップ4: 計算順序を決定して計算する
「トップダウン」(メモ化再帰)か「ボトムアップ」(ループによる漸化)かを決定し、dp[i]を計算するとき、それが依存する部分問題がすべて計算済みであることを確認します。
階段を上る問題では、ボトムアップ方式を採用し、
i=3までループします。i=n。
定番の例:フィボナッチ数列
フィボナッチ数列は動的計画法の最も直接的な例であり、その定義自体が状態遷移方程式です。
問題:フィボナッチ数列の第n項を求めよ。F(0)=0, F(1)=1, F(n)=F(n-1)+F(n-2) (n>=2)
例
"""動的計画法でフィボナッチ数を求める"""
if n < 2:
return n
# 空间优化写法
prev, curr = 0, 1 # F(0), F(1)
for _ in range(2, n + 1):
prev, curr = curr, prev + curr
return curr
# 测试数据
test_n = 10
print(fフィボナッチ数列の第 {test_n} 項は: {fibonacci(test_n)}) # 输出: 55
発展例:コインの両替
これは、最適部分構造を示す、より典型的な問題です。
問題の説明:整数配列が与えられますcoins、これは異なる額面のコインを表し、さらに整数が与えられますamount、これは合計金額を表します。合計金額をちょうど作るために必要な最小のコイン数を計算して返してください。どのコインの組み合わせでも合計金額を作れない場合は、返してください-1。各コインの数量は無制限であるとみなしてよい。
問題分析とDP設計
- 状態を定義する:
dp[i]合計金額をちょうど作るためのi最小コイン数を表す。 - 状態遷移方程式:金額
iに対して、それぞれの額面のコインを走査できます。coin。もしcoin <= iならば、金額iを作る1つの可能な方法は、まず金額i - coinを作り、それから1枚のcoin額面のコインを加えます。すべての可能性の中の最小値を求めます。したがって、方程式は次のように書けます:dp[i] = min(dp[i], dp[i - coin] + 1)、すべての条件を満たすcoin <= iのcoin。 - 初期条件:
dp[0] = 0、金額0を作るには0枚のコインが必要です。その他のdp[i]は非常に大きな数(例:amount + 1或float('inf'))に初期化され、一時的に作れないことを表します。 - 計算順序:ボトムアップで、
i=1まで計算しますi=amount。
コード実装
例
"""コイン両替 - 動的計画法"""
# dp 配列を初期化する。dp[i] は金額 i のときの最小コイン数
# 到達不可能な初期値 amount + 1 を設定する
dp = [amount + 1] * (amount + 1)
dp[0] = 0 # 金額 0 のときは 0 枚のコインが必要
# 外側のループ:すべての金額状態を走査する
for i in range(1, amount + 1):
# 内側のループ:すべてのコインの選択肢を走査する
for coin in coins:
# 現在のコインの額面が現在の金額以下の場合、そのコインの使用を検討できる
if coin <= i:
# 状態遷移:dp[i] は現在のコインを使わない解と、
# 現在のコインを使う解(すなわち dp[i-coin] + 1)のうちの小さい方の値
dp[i] = min(dp[i], dp[i - coin] + 1)
# dp[amount] が更新されていない(初期値のまま)場合、作り出せないことを示す
return dp[amount] if dp[amount] <= amount else -1
# テストデータ
coins = [1, 2, 5]
amount = 11
print(f"合計金額 {amount} を作るのに必要な最小コイン数は: {coin_change(coins, amount)}") # 出力: 3 (5+5+1)
実践演習
動的計画法の理解を深めるために、以下の問題を自力で解いてみてください:
練習1:最大部分配列の和
整数配列が与えられます。nums、その中から和が最大となる連続する部分配列を見つけ、その最大和を返してください。
例:
输入:nums = [-2,1,-3,4,-1,2,1,-5,4] 输出:6 解释:连续子数组 [4,-1,2,1] 的和最大,为 6。
ヒント:
- 定義します
dp[i]を「先頭からi番目の要素で終わる連続部分配列の最大和」とする。 - 状態遷移方程式:
dp[i] = max(nums[i], dp[i-1] + nums[i])。 - 最終的な答えはすべての
dp[i]の中の最大値です。
練習2:最長増加部分列
整数配列が与えられます。nums、その中で最長の狭義増加部分列の長さを見つけてください。
例:
输入:nums = [10,9,2,5,3,7,101,18] 输出:4 解释:最长递增子序列是 [2,3,7,101],因此长度为 4。
ヒント:
- 定義します
dp[i]を「先頭からi番目の数字で終わる最長増加部分列の長さ」とする。 - それぞれの
iについて、走査する必要があります。jから0到i-1もしnums[i] > nums[j]ならば、dp[i] = max(dp[i], dp[j] + 1)。 - 初期状態では、それぞれの
dp[i]は少なくとも1です(自身のみを含む)。
