mirror of
https://github.com/krahets/hello-algo.git
synced 2026-10-31 04:34:47 +08:00
7257641e0e
* Retranslate the complete Japanese online edition from Chinese * Fit Japanese homepage labels and localize heading permalinks * Point Japanese contribution instructions to the Japanese preview * Replace locale conditionals with multilingual UI tables
112 lines
7.0 KiB
Markdown
112 lines
7.0 KiB
Markdown
# 練習問題
|
|
|
|
## 知識の確認
|
|
|
|
### 動的計画法に適した場面
|
|
|
|
ある生徒が「漸化式を書けるなら、必ず動的計画法を使うべきだ」と言いました。
|
|
次の各作業には、動的計画法、バックトラッキング、または `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. 同じ反復内で現在の品物を重複して選ばないよう、容量は必ず大きい順に更新します
|