hello-algo/ja/docs/chapter_dynamic_programming/exercises.md

練習問題

知識の確認

動的計画法に適した場面

ある生徒が「漸化式を書けるなら、必ず動的計画法を使うべきだ」と言いました。 次の各作業には、動的計画法、バックトラッキング、または dp 表を作らずループや数式を使う方法のどれがより適しているかを判断し、主な理由を一つ書いてください。

1. 額面 [1, 3, 4] の硬貨で金額 6 を作るための最少枚数を求めます。各硬貨は何枚でも使えます。

2. [1, 2, 3] の全順列を出力します。

3. 1 + 2 + \dots + n を計算します。

   動的計画法に適していると判断した作業については、dp[i] が何を表すかも説明してください。

??? success "解答例"

1. 動的計画法に適しています。`dp[i]` を、金額 `i` を作るために必要な硬貨の最少枚数とします。
    `i` 以下の額面の各硬貨 `c` について `dp[i-c] + 1` を答えの候補とし、
    その最小値を取ります。異なる選択でも同じ金額に繰り返し行き着き、大きな金額の最適解も小さな金額の最適解から構成できます。
    金額 6 の答えは、`3 + 3` の 2 枚です。

2. バックトラッキングを使います。求められるのは 6 個すべての順列を一つずつ生成することであり、バックトラッキングなら、一つを選んで探索を進め、
    選択を取り消して別の分岐を試す作業を体系的に行えます。どの方法でも、実際に順列を出力するときには列挙を省略できません。

3. ループまたは等差数列の公式で十分です。`S(i) = S(i-1) + i` と書けますが、`S(i)` は一つの小さな `S(i-1)` だけに依存し、
    各部分和は一回計算すれば済みます。重複する部分問題がないため、`dp` 表は不要です。「漸化式を書ける」ことと「動的計画法が必要」なことは同じではありません。

ナップサックの表の一マスを計算する

0-1 ナップサック問題で、品物の重さは wgt = [1, 2, 3]、価値は val = [5, 11, 15]、容量は 4 です。 dp[i][c] は、最初の i 個の品物だけを考え、容量の上限を c としたときに得られる最大の価値を表します。 ナップサックをちょうど満杯にする必要はありません。

状態 dp[3][4] だけを計算します。dp[2][4] = 16、dp[2][1] = 5 は分かっているものとします。

1. 3 番目の品物を選ばない場合、価値の候補はいくつですか。
2. 3 番目の品物を選ぶ場合、残りの容量と価値の候補はいくつですか。
3. dp[3][4] はいくつになりますか。どの品物を選ぶことに対応しますか。

??? success "解答例"

1. 3 番目の品物を選ばない場合は、最初の二つの品物の結果を使い、候補は `dp[2][4] = 16` です。

2. 3 番目の品物の重さは 3 なので、入れた後の残りの容量は $4-3=1$ です。価値の候補は
    `dp[2][1] + 15 = 5 + 15 = 20` です。

3. 16 と 20 を比較して、`dp[3][4] = 20` となります。これは 1 番目と 3 番目の品物を選ぶことに対応し、
    重さの合計は $1+3=4$、価値の合計は $5+15=20$ です。

    この状態の計算は、0-1 ナップサック問題での一回の「選ぶか選ばないか」の比較を表しています。

ナップサックの容量を更新する順序

0-1 ナップサック問題に、重さ 2、価値 5 の品物が一つだけあります。ナップサックの容量は 4 です。 各品物は一回だけ選べ、初期の一次元配列は dp = [0, 0, 0, 0, 0] です。

ある生徒がこの品物を処理するとき、容量 2 から 4 の順に更新しました。

• dp[2] を更新して 5 を得ました。
• dp[3] を更新して、ここでも 5 を得ました。
• dp[4] の更新では、今求めた dp[2] を使ったため、dp[4] = 10 となりました。

1. dp[4] = 10 は正しい結果ですか。理由も説明してください。
2. 「各品物は一回だけ選べる」という条件から、dp[4] はいくつになるべきですか。
3. 各品物を処理するとき、容量は大きい順と小さい順のどちらで更新すべきですか。その順序によって、どの問題を避けられますか。

??? success "解答例"

1. 正しくありません。価値 10 は、価値 5 の同じ品物を二回入れたことに相当し、
    「各品物は一回だけ選べる」という条件に違反します。

2. 入れられるのはこの一つの品物だけなので、正しい `dp[4]` は 5 です。

3. 容量は大きい順、つまり 4、3、2 の順に更新します。
    そうすれば、`dp[c]` を計算するときに読み取る `dp[c-2]` は、まだ現在の品物を処理する前の結果なので、
    同じ反復内で現在の品物を重複して使わずに済みます。

プログラミング演習

階段の上り方の数

n 段の階段があります。一回に 1 段か 2 段だけ上れ、ちょうど第 n 段に到達する必要があります。 異なる上り方が何通りあるかを計算してください。n >= 1 とし、各歩で 1 段進むか 2 段進むかによってのみ上り方を区別します。 一次元の動的計画法の配列を使い、二つの状態だけを残す空間最適化は、ここでは行わないでください。

??? tip "解くためのヒント"

1. 第 i 段に到達する最後の一歩は、1 段または 2 段しか進めません
2. したがって、dp[i] = dp[i-1] + dp[i-2] が成り立ちます
3. まず n が 1 と 2 の場合を処理し、第 3 段から表を埋めます

LeetCode{ .rounded-button .exercise-button target="_blank" rel="noopener noreferrer" }

0-1 ナップサック問題

同じ長さの配列 wgt と val が与えられます。品物 i の重さは正の整数 wgt[i]、価値は非負整数 val[i] です。 ナップサックの容量 cap は非負整数です。各品物は一回だけ選べます。重さの合計が cap を超えない範囲で、 ナップサックに入れられる価値の合計の最大値を求めてください。一次元の動的計画法で実装してください。

??? tip "解くためのヒント"

1. 長さ cap + 1 の配列 dp を初期化します。dp[c] は、容量の上限が c の場合の最大の価値を表します
2. 品物 i を処理するときは、「選ばない」場合の dp[c] と、「選ぶ」場合の dp[c-wgt[i]] + val[i] を比較します
3. 同じ反復内で現在の品物を重複して選ばないよう、容量は必ず大きい順に更新します