Pythonで解く【初中級者が解くべき過去問精選 100 問】(034 - 038 動的計画法：ナップザック DP基本)

# 1. 目的
[初中級者が解くべき過去問精選 100 問](https://qiita.com/e869120/items/eb50fdaece12be418faa)をPythonで解きます。
すべて解き終わるころに水色になっていることが目標です。

本記事は「034 - 038 動的計画法：ナップザック DP」です。

# 2. 総括
```DP``` はかなり苦労しました。```BFS```、```DFS```もかなり苦労しましたが、それ以上に```DP```が少しだけわかるまでかなり悩みました。
やったことは、```BFS```、```DFS```のときと同じで、解説をよみつつ、```AC```の回答例を理解できるまで1行ずつデバックで追っていくのみです。
また、精選100問の```DP```が最初まったくできなかったので、先に[Typical DP Contest](https://atcoder.jp/contests/tdpc/tasks)を```A~L```まで解いてから（というか回答例を見ながら理解した）着手しました。
すると、少しだけ解けるるようになっていました。


# 3. 本編
## 034 - 038 動的計画法：ナップザック DP基本

### 034. [ALDS_10_A - フィボナッチ数](http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_10_A&lang=ja)
#### 回答
```python

n = int(input())
dp = [0] * (n + 1)

dp[0] = 1
dp[1] = 1

for i in range(2, n+1):
    dp[i] = dp[i - 1] + dp[i -2]

print(dp[n])

```

下記のように再帰で書くと```TLE```で通りませんので``DP```で解く必要がある、ということがわかる問題です。

```python

# これではTLE
num = int(input())

def fib(num):
    if num == 0:
        return 1
    if num == 1:
        return 1

    return fib(num - 1) + fib(num - 2)

print(fib(num))


```


---

### 035. [DPL_1_B - 0,1ナップザック問題](http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DPL_1_B&lang=ja)
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/668985/079a86a6-890f-2dd5-840b-febd844793d7.png)

#### 回答
```python

N, W = map(int, input().split()) # N個の品物、Wが重さの容量
p = [(0, 0)] + [tuple(map(int, input().split())) for _ in range(N)] # 品物-> (価値, 重さ)
dp = [[0] * (W+1) for _ in range(N+1)] # 縦が品物の番号、横が現在の容量、dpの中身が最大の価値とする

for i in range(1, N+1):
    for j in range(1, W+1):
        
        if j-p[i][1] >= 0:
            dp[i][j] = max(dp[i-1][j],
                           dp[i-1][j-p[i][1]] + p[i][0])
        else:
            dp[i][j] = dp[i-1][j]

print(dp[N][W])

```

典型中の典型です。
1次元dpで書く方法もあるようですが、僕はこのほうが書きやすいです。



---

### 036. [DPL_1_C - ナップザック問題](http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DPL_1_C&lang=ja)
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/668985/13c42997-628a-1f64-4e15-253a411cc272.png)

#### 回答
```python

N, W = map(int, input().split()) # Nは品物の種類、Wは上限の重さ
p = [(0, 0)] + [tuple(map(int, input().split())) for _ in range(N)] # (価値, 重さ)
dp = [[0] * (W+1) for _ in range(N+1)]

for i in range(1, N+1):
    for j in range(1, W+1):

        if j-p[i][1] >= 0:
            dp[i][j] = max(dp[i-1][j],
                           dp[i][j-p[i][1]] + p[i][0])
        else:
            dp[i][j] = dp[i-1][j]

print(dp[N][W])


```

問題35との違いは、同種類の製品を重複して選べる点ですので、コードもその部分だけ修正してやります。
具体的には、

```python

dp[i][j] = max(dp[i-1][j],
               dp[i-1][j-p[i][1]] + p[i][0])
```

と


```python

dp[i][j] = max(dp[i-1][j],
               dp[i][j-p[i][1]] + p[i][0])

```
で、```max```の中身が違います。問題35は「添え字iの一つ前から重さを引いて自分の価値を足す」という形でしたが、問題36は「自分の重さを引いて自分の価値を足す」です。

---



### 037. [DPL_1_A - コイン問題](http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DPL_1_A&lang=ja)
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/668985/d8b7a93a-4813-d958-3942-f6b824a1c1d1.png)

#### 回答
```python

INF = float('inf')
n, m = map(int, input().split())
coins = [0] + list(map(int, input().split()))
dp = [[INF] * (n+1) for _ in range(m+1)]

dp[0][0] = 0

for i in range(1, m+1):
    for j in range(n+1):
        
        if j-coins[i] >= 0:
            dp[i][j] = min(dp[i-1][j-coins[i]] + 1,
                           dp[i][j-coins[i]] + 1,
                           dp[i-1][j])
        else:
            dp[i][j] = dp[i-1][j]

print(dp[m][n])

```

コイン問題も典型で、ナップサックと考え方はほぼ同じです。

---

### 038. [ALDS_10_C - 最長共通部分列](http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_10_C&lang=ja)
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/668985/5e1f24b3-b9b6-6701-7908-aff02884d13c.png)

#### 回答
```python

# これだと通るけど好きじゃない。
def main(A, B):
    dp = [0] * (len(B)+1)

    for a in A:
        before = dp[:]
        for j in range(1, len(B)+1):
            
            if a == B[j-1]:
                dp[j] = before[j-1] + 1
            elif dp[j] < dp[j-1]:
                dp[j] = dp[j-1]
                            
    return dp[-1]


if __name__ == "__main__":
    q = int(input())
    for _ in range(q):
        A = list(input())
        B = list(input())
        print(main(A, B))

```

問題34~37と同じように書くと下記のようになります。僕はこの書き方が一番わかりやすいし、最長共通部分列の復元も行いやすいので好きです。
しかしシステム上は下記のように書くと```TLE```となってしまうので、いろいろ工夫して高速化をしたのが上記の回答です。

```python

# これだとTLE。復元はやりやすい。
q = int(input())

answer_list = []
for _ in range(q):
    A = [''] + list(input())
    B = [''] + list(input())
    dp = [[0] * (len(B)) for _ in range(len(A))]

    for i in range(1, len(A)):
        for j in range(1, len(B)):
            
            if A[i] == B[j]:
                dp[i][j] = dp[i-1][j-1] + 1
            else:
                dp[i][j] = max(dp[i][j-1],
                               dp[i-1][j])

    print(dp[len(A)-1][len(B)-1])

```

特に文字Aについて、```for i in range(1, len(A)):```で回した場合にくらべ```for a in A:```でまわしたほうが早いようです。やはり、リストに添え字でアクセスするのが結構遅いのかもしれません。


---