企业官网建设流程全解析

Hello Algo 動的計画法の章末演習を完全解説――適用判定・0-1ナップサックの状態遷移と逆順更新をコードで理解する

【免费下载链接】hello-algo《Hello 算法》：动画图解、一键运行的数据结构与算法教程。支持简中、繁中、English、日本語，提供 Python, Java, C++, C, C#, JS, Go, Swift, Rust, Ruby, Kotlin, TS, Dart 等代码实现项目地址: https://gitcode.com/GitHub_Trending/he/hello-algo

本記事は、ja/docs/chapter_dynamic_programming/章の章末演習（exercises.md）を題材に、動的計画法（dynamic programming）が適する問題の判定方法、0-1ナップサック問題の dp テーブル状態遷移、容量走査の順序が解の正しさを左右する仕組み、そして一次元 dp 配列による実装を体系的に解説します。各設問の解答を、倉庫内の Python 実装（ja/codes/python/chapter_dynamic_programming/）と対応づけながら読み解くことで、「漸化式が書ける」ことと「DP が必要なこと」の違い、逆順ループの本質的な意味を、手を動かして検証できるようになることをゴールとします。

全体像：演習が問う 4 つの核心

章末演習は「確認問題 3 題」と「プログラミング演習 2 題」で構成され、それぞれが DP の最重要論点をカバーしています。

DP の基本概念（dp テーブル、初期状態、状態遷移方程式、空間最適化）の定義は intro_to_dynamic_programming.md で確認できます。本演習はその知識を「判定力」と「実装力」に転化させる位置づけの章です。

確認問題 1：動的計画法が適している場面を判定する

問題設定：「漸化式を書けるなら、必ず動的計画法を使うべきです」という主張に対して、以下の 3 つの処理それぞれにDP・バックトラッキング・dp テーブルを使わないループや数式のどれが適するかを判断し、理由を答えなさい。

1-A. 額面[1, 3, 4]の硬貨で金額 6 を作る最小枚数（各硬貨は何度でも使用可）

適する手法：動的計画法。

dp[i]を「金額iを作るのに必要な最小硬貨枚数」と定義します。金額i以下の各硬貨cについて、dp[i - c] + 1を候補とし、その最小値を採用します。

dp[i] = min(dp[i - c] + 1) （c ∈ {1, 3, 4} かつ c ≤ i の範囲）

• 同じ金額iが、異なる硬貨の組み合わせの中に繰り返し登場するため、重複部分問題が大量に発生します。DP は各金額を 1 回だけ計算することでこれを吸収します。
• より大きな金額の最適解は、より小さな金額の最適解から構築できる（最適部分構造）ため、漸化式が成立します。
• 金額 6 の答えは2 枚（3 + 3）です。dp[6] = min(dp[5] + 1, dp[3] + 1, dp[2] + 1)となり、dp[3] = 1なのでdp[3] + 1 = 2が最小値として選ばれます。

この問題は各硬貨を無制限に使える「コイン両替（最小枚数版）」であり、倉庫の coin_change.py にdpテーブル版coin_change_dpと空間最適化版coin_change_dp_compの 2 実装が用意されています。後者は「各硬貨を何度でも使える」ため容量を順方向に走査します（確認問題 3 の対比で重要です）。

1-B.[1, 2, 3]のすべての順列（全 6 通り）を出力する

適する手法：バックトラッキング。

これは「結果の列挙がそもそもの目的」の問題です。1 つの選択を試して探索を進め、選択を取り消して別の分岐を試すバックトラッキングが自然に対応します。どんな手法を使っても、6 通りの順列を実際に出力する以上、列挙そのものを省略することはできません。

一方 DP は「ある状態の最適値（あるいは個数）」を求める手法であり、全ての解候補を列挙する用途には向きません。倉庫のバックトラッキング章（ja/codes/python/chapter_backtracking/）にpermutations_i.pyをはじめとした順列生成の実装があります。判定のポイントは「列挙が目的か、最適値・個数の計算が目的か」です。

1-C.1 + 2 + ... + nを計算する

適する手法：ループ、または等差数列の公式で十分。

確かにS(i) = S(i - 1) + iという漸化式は書けます。しかしS(i)の計算が依存するのは直前のS(i - 1)だけであり、各部分和は 1 回ずつ計算すれば済みます。つまり重複部分問題が存在しません。DP の恩恵（重複計算の排除）を受けられないため、dpテーブルは不要です。

重要：「漸化式を書けること」と「動的計画法が必要であること」は別物です。DP が威力を発揮するのは、①重複部分問題があり、②最適部分構造（部分問題の最適解から全体の最適解が組み立てられる）が成り立つ場合に限られます。この性質の詳しい議論は dp_problem_features.md で展開されています。

確認問題 2：dp[3][4]の一発計算で読み解く 0-1 ナップサック

問題設定：品物の重さwgt = [1, 2, 3]、価値val = [5, 11, 15]、容量 4 の 0-1 ナップサックを考えます。dp[i][c]は「先頭からi個の品物だけを考え、容量上限がcのときの最大価値」を表します（ナップサックをちょうど満たす必要はありません）。既知の値dp[2][4] = 16、dp[2][1] = 5を用いてdp[3][4]を計算します。

遷移の基本形：入れるか、入れないか

3 番目の品物（重さ 3、価値 15）に対する判断は次の 2 択です。

1. 3 番目の品物を選ばない場合

最初の 2 個の品物による結果をそのまま使うので、候補価値はdp[2][4] = 16です。

2. 3 番目の品物を選ぶ場合

品物の重さは 3 なので、入れた後の残り容量は4 - 3 = 1です。残り容量 1 に対する最適値dp[2][1] = 5に品物の価値 15 を加えて、候補価値はdp[2][1] + 15 = 5 + 15 = 20です。

3. 両者の比較

max(16, 20) = 20なのでdp[3][4] = 20とします。これは**品物 1（重さ 1、価値 5）と品物 3（重さ 3、価値 15）**を選ぶことに対応し、総重量は1 + 3 = 4、総価値は5 + 15 = 20で整合します。

この 1 セルぶんの計算が、0-1 ナップサックにおける「選ぶか、選ばないか」の 1 回の比較そのものです。一般的な状態遷移式は次式で表されます。

dp[i][c] = max(dp[i-1][c], dp[i-1][c - wgt[i-1]] + val[i-1])

倉庫の knapsack.py に実装されたknapsack_dpは、まさにこの式をi = 1..n、c = 1..capの二重ループで全セルに適用します。容量cが品物の重さに満たない場合（wgt[i-1] > c）は「入れない」選択しかできないためdp[i][c] = dp[i-1][c]になる点も、上記コードの分岐（52〜57 行）と対応します。

確認問題 3：容量の更新順序が「同じ品物を二度使う」を防ぐ

問題設定：重さ 2・価値 5 の品物が1 つだけあり、容量 4 のナップサックに詰めます（各品物 1 回まで）。一次元配列は初期状態dp = [0, 0, 0, 0, 0]です。ある生徒がこの品物を処理する際、容量を **2 → 3 → 4 の順（小→大）**で更新しました。

順方向更新で何が起きるか

• dp[2]を更新すると 5 になる。
• dp[3]を更新しても 5 になる（残り容量 1 には詰められないため）。
• dp[4]を更新するとき、つい先ほど更新したばかりのdp[2] = 5を参照してしまうため、dp[4] = dp[2] + 5 = 10になってしまう。

各問の解答

Q1.dp[4] = 10は正しいか？

正しくありません。価値 10 は「価値 5 の品物を2 回入れた」ことに相当し、「各品物は 1 回までしか選べない」という 0-1 ナップサックの条件に反します。この品物は 1 個しか存在しないため、10 の価値を達成することは不可能です。

Q2. 正しいdp[4]はいくつか？

ナップサックに入れられるのはこの品物 1 つだけなので、正しいdp[4]は5です。

Q3. 更新順序は大→小か、小→大か？

容量が大きいほうから小さいほう（4 → 3 → 2）へ更新します。この順序なら、dp[c]の計算時に読み取るdp[c - 2]は「現在の品物を処理する前の値」のままなので、同一ループ内で現在の品物を繰り返し使う（同一品物を 2 回以上選ぶ）ことを防げます。

ソースコードでの検証

空間最適化済みの 0-1 ナップサックは knapsack.py のknapsack_dp_compで実装されており、for c in range(cap, 0, -1)のように容量を逆順に走査しています（67〜69 行）。この逆順ループが、まさに上記の「同一ループ内での再使用防止」を保証する核心です。

対照的に、各品物を無限に使える完全ナップサックの空間最適化版unbounded_knapsack_dp_comp（unbounded_knapsack.py、for c in range(1, cap + 1)）は順方向に走査します。コイン両替のcoin_change_dp_comp（coin_change.py）も同様に順方向です。つまり走査の向きは「品物を再利用できるかどうか」をコードに反映したものであり、0-1 型と無制限型でループが正反対になる点が本設問の最重要ポイントです。詳しい理論は knapsack_problem.md と unbounded_knapsack_problem.md を参照してください。

プログラミング演習 1：階段を上る方法の数を一次元 dp で実装する

問題：n段の階段があり、1 回に 1 段または 2 段だけ上れます。ちょうどn段目に到達する異なる上り方の総数を求めてください（n >= 1）。各上り方は「各回に 1 段進むか 2 段進むか」だけで区別します。一次元の dp 配列を使い、2 状態だけを残す空間最適化（ローリング変数）は使わないことが条件です。

解法のポイント（ヒント）

1. i段目へ到達する最後の一歩は、i - 1段目から 1 段上がるか、i - 2段目から 2 段上がるかのどちらかです。
2. したがって状態遷移式はdp[i] = dp[i-1] + dp[i-2]になります。
3. まずn = 1、n = 2の場合を処理し（それぞれ 1 通り、2 通り）、3段目から表を埋めます。

解答例

def climbing_stairs(n: int) -> int: """階段登り：一次元 dp テーブル（空間最適化なし）""" if n == 1 or n == 2: return n # dp[i]: i 段目まで上る方法の数 dp = [0] * (n + 1) dp[1], dp[2] = 1, 2 for i in range(3, n + 1): dp[i] = dp[i - 1] + dp[i - 2] return dp[n]

倉庫実装との対応と実行方法

上記の骨格は、倉庫の climbing_stairs_dp.py にあるclimbing_stairs_dp（8〜19 行）と完全に対応します。同ファイルはif __name__ == "__main__"のドライバコードを持ち、n = 9に対して「9 段の階段を上る方法は全部で 55 通りです」と出力するようになっています（n = 9に対する答え 55 は、上記のコードで検算可能です）。

このファイルには、演習が禁止した 2 状態だけの空間最適化版climbing_stairs_dp_comp（22〜29 行、a, b = b, a + bのローリング変数方式）も併載されています。両者を見比べることで、同じ問題でも「全状態を保持するか・直前 2 状態だけ保持するか」で空間計算量がO(n)からO(1)に変わることを実感できます。なお、なぜこの問題でバックトラッキング（O(2^n)）→ メモ化探索（O(n)）→ DP と段階的に効率が改善されるかは、intro_to_dynamic_programming.md の再帰木の図解（climbing_stairs_backtrack→climbing_stairs_dfs→climbing_stairs_dfs_mem→climbing_stairs_dpの 4 実装）で確認できます。

プログラミング演習 2：0-1 ナップサックを一次元 dp で実装する

問題：同じ長さの配列wgtとvalが与えられます。i番目の品物の重さは正の整数wgt[i]、価値は 0 以上の整数val[i]、ナップサックの容量capは 0 以上の整数です。各品物は 1 回までしか選べず、総重量がcap以下という条件のもとで、ナップサックに入れられる最大の総価値を求めてください。一次元の動的計画法で実装します。

解法のポイント（ヒント）

1. 長さcap + 1の配列dpを初期化します。dp[c]は「容量上限がcのときの最大価値」を表します（dp[0] = 0）。
2. 品物iを処理するとき、「選ばない」場合のdp[c]と、「選ぶ」場合のdp[c - wgt[i]] + val[i]を比較し、大きいほうを採用します。
3. 同じループ内で現在の品物を繰り返し選ばないよう、容量は必ず大きいほうから小さいほうへ更新します（確認問題 3 で学んだ逆順走査）。

解答例

def knapsack_01(wgt: list[int], val: list[int], cap: int) -> int: """0-1 ナップサック：一次元 dp（逆順走査）""" n = len(wgt) dp = [0] * (cap + 1) for i in range(1, n + 1): for c in range(cap, wgt[i - 1] - 1, -1): dp[c] = max(dp[c], dp[c - wgt[i - 1]] + val[i - 1]) return dp[cap]

なぜ逆順走査が必須なのか

dp[c]の更新式はdp[c] = max(dp[c], dp[c - wgt[i-1]] + val[i-1])であり、より小さい添字c - wgt[i-1]の値を読み取ります。容量を小さいほうから大きいほうへ更新すると、dp[c - wgt[i-1]]がすでに現在の品物を使って更新済みの値になり、同一品物を 2 回以上選んだことに相当する不正な結果（確認問題 3 のdp[4] = 10と同じ現象）が生じます。逆順（大→小）なら、参照する値は常に「前の品物までの最適値」なので正しくなります。

倉庫の knapsack.py では、この一次元版がknapsack_dp_comp（61〜76 行）として実装されており、二次元テーブル版knapsack_dp（44〜58 行）とドライバコード上で出力が一致することを確認できます（wgt = [10, 20, 30, 40, 50]、val = [50, 120, 150, 210, 240]、cap = 50の例で 4 手法すべて同じ最大価値を返します）。二次元版が空間計算量O(n × cap)なのに対し、一次元版はO(cap)に削減でき、時間計算量はどちらもO(n × cap)です。

なお「各品物を何度でも使える」完全ナップサック版は、unbounded_knapsack.py のunbounded_knapsack_dp_compにあり、ループが順方向になる点だけが 0-1 版と異なります。演習 1 の階段上りは「1 段 / 2 段」という事実上の再利用なし遷移、演習 2 の 0-1 ナップサックは逆順走査、完全ナップサックは順方向走査――この 3 つを並べて読むことで、dp 遷移の「方向性」への理解が一気に深まります。

まとめ：演習を通じて身につく DP の判定力と実装力

本章末演習の要点を振り返ります。

• 適用判定：重複部分問題と最適部分構造があるなら DP、解の列挙が目的ならバックトラッキング、依存が直前 1 状態だけで重複がないなら素直なループや公式で十分です。「漸化式が書ける = DP が必要」ではありません。
• 状態遷移：0-1 ナップサックのdp[i][c]は「選ばない（dp[i-1][c]）」と「選ぶ（dp[i-1][c-wgt[i-1]] + val[i-1]）」の比較で埋まり、1 セルの計算がそのまま遷移式の縮図です。
• 走査順序：一次元化したとき、0-1 型（再利用不可）は大→小の逆順、無制限型（再利用可）は小→大の順方向。この対比が DP 実装の最大の落とし穴を回避します。
• 実装力：一次元 dp は空間計算量をO(cap)やO(n)に落とせる一方、演習のように「全状態を保持する」指定がある場合は省略せず dp テーブルを完備するのが正解です。

続けて学習する場合は、knapsack_problem.md と unbounded_knapsack_problem.md でナップサック問題全体の設計フローを、dp_solution_pipeline.md で「問題分析 → 状態定義 → 遷移式 → 初期化 → 実装」という DP 問題の標準的な解き方を体系的に学べます。また、各設問の検算には ja/codes/python/chapter_dynamic_programming/ の各ドライバコードをそのまま実行するのが最も手軽です。

【免费下载链接】hello-algo《Hello 算法》：动画图解、一键运行的数据结构与算法教程。支持简中、繁中、English、日本語，提供 Python, Java, C++, C, C#, JS, Go, Swift, Rust, Ruby, Kotlin, TS, Dart 等代码实现项目地址: https://gitcode.com/GitHub_Trending/he/hello-algo