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 の最重要論点をカバーしています。設問論点対応するソース確認問題 1DP・バックトラッキング・ループの使い分け判定climbing_stairs_backtrack.py、coin_change.py確認問題 20-1 ナップサックのdp[i][c]一発計算と状態遷移式knapsack.py確認問題 3容量走査の向きと「同一品物の再使用」の防止knapsack.py、unbounded_knapsack.pyプログラミング演習 1・2一次元 dp 配列による階段上り / 0-1 ナップサックの実装climbing_stairs_dp.py、knapsack.pyDP の基本概念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 で展開されています。確認問題 2dp[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_compunbounded_knapsack.py、for c in range(1, cap 1)は順方向に走査します。コイン両替のcoin_change_dp_compcoin_change.pyも同様に順方向です。つまり走査の向きは「品物を再利用できるかどうか」をコードに反映したものであり、0-1 型と無制限型でループが正反対になる点が本設問の最重要ポイントです。詳しい理論は knapsack_problem.md と unbounded_knapsack_problem.md を参照してください。プログラミング演習 1階段を上る方法の数を一次元 dp で実装する問題n段の階段があり、1 回に 1 段または 2 段だけ上れます。ちょうどn段目に到達する異なる上り方の総数を求めてくださいn 1。各上り方は「各回に 1 段進むか 2 段進むか」だけで区別します。一次元の dp 配列を使い、2 状態だけを残す空間最適化ローリング変数は使わないことが条件です。解法のポイントヒントi段目へ到達する最後の一歩は、i - 1段目から 1 段上がるか、i - 2段目から 2 段上がるかのどちらかです。したがって状態遷移式はdp[i] dp[i-1] dp[i-2]になります。まず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_dp8〜19 行と完全に対応します。同ファイルはif __name__ __main__のドライバコードを持ち、n 9に対して「9 段の階段を上る方法は全部で 55 通りです」と出力するようになっていますn 9に対する答え 55 は、上記のコードで検算可能です。このファイルには、演習が禁止した 2 状態だけの空間最適化版climbing_stairs_dp_comp22〜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 実装で確認できます。プログラミング演習 20-1 ナップサックを一次元 dp で実装する問題同じ長さの配列wgtとvalが与えられます。i番目の品物の重さは正の整数wgt[i]、価値は 0 以上の整数val[i]、ナップサックの容量capは 0 以上の整数です。各品物は 1 回までしか選べず、総重量がcap以下という条件のもとで、ナップサックに入れられる最大の総価値を求めてください。一次元の動的計画法で実装します。解法のポイントヒント長さcap 1の配列dpを初期化します。dp[c]は「容量上限がcのときの最大価値」を表しますdp[0] 0。品物iを処理するとき、「選ばない」場合のdp[c]と、「選ぶ」場合のdp[c - wgt[i]] val[i]を比較し、大きいほうを採用します。同じループ内で現在の品物を繰り返し選ばないよう、容量は必ず大きいほうから小さいほうへ更新します確認問題 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_comp61〜76 行として実装されており、二次元テーブル版knapsack_dp44〜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创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考 Hello Algo 動的計画法の章末演習を完全解説――適用判定・0-1ナップサックの状態遷移と逆順更新をコードで理解する
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 の最重要論点をカバーしています。設問論点対応するソース確認問題 1DP・バックトラッキング・ループの使い分け判定climbing_stairs_backtrack.py、coin_change.py確認問題 20-1 ナップサックのdp[i][c]一発計算と状態遷移式knapsack.py確認問題 3容量走査の向きと「同一品物の再使用」の防止knapsack.py、unbounded_knapsack.pyプログラミング演習 1・2一次元 dp 配列による階段上り / 0-1 ナップサックの実装climbing_stairs_dp.py、knapsack.pyDP の基本概念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 で展開されています。確認問題 2dp[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_compunbounded_knapsack.py、for c in range(1, cap 1)は順方向に走査します。コイン両替のcoin_change_dp_compcoin_change.pyも同様に順方向です。つまり走査の向きは「品物を再利用できるかどうか」をコードに反映したものであり、0-1 型と無制限型でループが正反対になる点が本設問の最重要ポイントです。詳しい理論は knapsack_problem.md と unbounded_knapsack_problem.md を参照してください。プログラミング演習 1階段を上る方法の数を一次元 dp で実装する問題n段の階段があり、1 回に 1 段または 2 段だけ上れます。ちょうどn段目に到達する異なる上り方の総数を求めてくださいn 1。各上り方は「各回に 1 段進むか 2 段進むか」だけで区別します。一次元の dp 配列を使い、2 状態だけを残す空間最適化ローリング変数は使わないことが条件です。解法のポイントヒントi段目へ到達する最後の一歩は、i - 1段目から 1 段上がるか、i - 2段目から 2 段上がるかのどちらかです。したがって状態遷移式はdp[i] dp[i-1] dp[i-2]になります。まず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_dp8〜19 行と完全に対応します。同ファイルはif __name__ __main__のドライバコードを持ち、n 9に対して「9 段の階段を上る方法は全部で 55 通りです」と出力するようになっていますn 9に対する答え 55 は、上記のコードで検算可能です。このファイルには、演習が禁止した 2 状態だけの空間最適化版climbing_stairs_dp_comp22〜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 実装で確認できます。プログラミング演習 20-1 ナップサックを一次元 dp で実装する問題同じ長さの配列wgtとvalが与えられます。i番目の品物の重さは正の整数wgt[i]、価値は 0 以上の整数val[i]、ナップサックの容量capは 0 以上の整数です。各品物は 1 回までしか選べず、総重量がcap以下という条件のもとで、ナップサックに入れられる最大の総価値を求めてください。一次元の動的計画法で実装します。解法のポイントヒント長さcap 1の配列dpを初期化します。dp[c]は「容量上限がcのときの最大価値」を表しますdp[0] 0。品物iを処理するとき、「選ばない」場合のdp[c]と、「選ぶ」場合のdp[c - wgt[i]] val[i]を比較し、大きいほうを採用します。同じループ内で現在の品物を繰り返し選ばないよう、容量は必ず大きいほうから小さいほうへ更新します確認問題 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_comp61〜76 行として実装されており、二次元テーブル版knapsack_dp44〜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创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考