# 練習問題

## 知識の確認

### 動的計画法に適した場面

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

<!-- numbered-subquestions -->

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` は分かっているものとします。

<!-- numbered-subquestions -->

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` となりました。

<!-- numbered-subquestions -->

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](https://leetcode.com/problems/climbing-stairs/){ .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. 同じ反復内で現在の品物を重複して選ばないよう、容量は必ず大きい順に更新します