動的計画法の基本を理解するためのAtCoder問題5選とPython解答例

[Supership](https://supership.jp/)の名畑です。[手塚治虫 ブラック・ジャック展](https://blackjackex.roppongihills.com/)は本当に熱い展示でした。多くの方が短くとも3時間程度は滞在していたのではないでしょうか。

## はじめに

前に「[AtCoder アルゴリズムと数学 009 - Brute Force 2 解答例(Pythonでのbit全探索 / 動的計画法のシンプルなコード例)](https://qiita.com/nabata/items/122d7b2aa78391a8cae6)」という記事で[動的計画法](https://ja.wikipedia.org/wiki/%E5%8B%95%E7%9A%84%E8%A8%88%E7%94%BB%E6%B3%95)について書きました。

[AtCoder](https://atcoder.jp/)をやる上では避けては通れない**動的計画法**ですが、私、本当に苦手なんです。すぐにその内容が頭から飛んでしまう。きちんと理解できていないってことなと思います。

未来の自分自身のため、AtCoderにおける**動的計画法**の基本的な問題を5問選んで **Python(PyPy 3.10-v7.3.12)** での解答例をここに残しておきます。見直し用です。
私と同じような方の役にも立つと嬉しいです。

かなり初歩的なため、すでにきっちり理解できている方にとっては物足りない内容かとは思います。

## 動的計画法とは

そもそも**動的計画法**とはなんなのか。
Wikipediaによると下記の説明でした。

> 動的計画法（どうてきけいかくほう、英: Dynamic Programming, DP）は、計算機科学の分野において、アルゴリズムの分類の1つである。対象となる問題を複数の部分問題に分割し、部分問題の計算結果を記録しながら解いていく手法を総称してこう呼ぶ。

と、文章で説明されてもぴんと来ない方のための5問になります。

## 1 - 部分和問題

**問題**：[アルゴリズムと数学 演習問題集 009 - Brute Force 2](https://atcoder.jp/contests/math-and-algorithm/tasks/math_and_algorithm_i)

先述の記事で取り上げた問題です。

正の整数が書かれた**N枚**のカードにおいて合計が**S**になる組み合わせがあるかを**Yes** or **No**で答えるという問題です。

たとえば**N**が**3**で、各カードを**A0**、**A1**、**A2**とします。
そして書かれた整数が**A0**は**1**、**A1**は**2**、**A2**は**3**だとします。

**A0**しかカードがない場合、とりうる合計値は**0**と**1**のみです。**A0**を選ぶか選ばないかの2択しかないので。

**A1**もある場合、とりうる合計値は下記の通りで**0**、**1**、**2**、**3**です。**0**と**1**に対してさらに**A1**を選ぶか選ばないかの2択が発生するため。

- 0 + 0 = 0
- 0 + 2 = 2
- 1 + 0 = 1
- 1 + 2 = 3

**A2**もある場合、とりうる合計値は下記です。

- 0 + 0 = 0
- 0 + 3 = 3
- 1 + 0 = 1
- 1 + 3 = 4
- 2 + 0 = 2
- 2 + 3 = 5
- 3 + 0 = 3
- 3 + 3 = 6

**0**、**1**、**2**、**3**、**4**、**5**、**6**です。
つまり、**S**がこの7つの中にあれば**Yes**となります。

コードにすると下記です。

```Python
N, S = map(int, input().split())
A = list(map(int, input().split()))
dp = [False] * (S + 1)  # 0〜Sまでの値をとりうるかを格納する配列
dp[0] = True  # 0のみTrueにしておく
for i in range(N):  # 0枚目から順番にカードを見ていく
    for j in reversed(range(0, S)):  # dpの値がループ途中で変わらないようにreversedしている
        if dp[j] and j + A[i] <= S:
            dp[j + A[i]] = True
if dp[S]:  # Sをとりうるか判定する
    print('Yes')
else:
    print('No')
```

## 2 - 部分和問題 - 最小値

**問題**：[アルゴリズムと数学 演習問題集 028 - Frog 1](https://atcoder.jp/contests/math-and-algorithm/tasks/dp_a)

**N個**の足場があり、それぞれの高さは**h**という配列に格納されています。
カエルは一つ先の足場か二つ先の足場にのみ移動でき、その際のコストは今いる足場との高さの差です。
カエルが**N個目**の足場にたどり着くまでのコストの総和の最小値を求めるという問題です。

先述の問題では値をとりうるか否かのみが求められましたが、この問題では最小値を求めます。

考え方は同じです。**1個目**の足場にたどり着くまでのコストの最小値、**2個目**の足場にたどり着くまでのコストの最小値……**N個目**の足場にたどり着くまでのコストの最小値を順番に求めていきます。

下記はコードです。コードを簡潔にしたかったため足場を**0〜N-1**としてあるのでご注意ください。

```Python
N = int(input())
h = list(map(int, input().split()))

# i個目の足場にたどり着くまでのコストの最小値を格納する配列
dp = [float('inf')] * N  # 初期値として無限大を入れておきます
dp[0] = 0  # 最初にいる足場までのコストを0とする

for i in range(0, N - 1):  # 最初の足場から最後の1個前の足場まで
    for dist in [1, 2]:  # 1つ先の足場に移動した時と2つ先の足場に移動した時のコストの最小値を記録する
        if i + dist < N:  # 移動可能である
            diff = abs(h[i + dist] - h[i])  # 高さの差
            if dp[i] + diff < dp[i + dist]:  # 最小値である
                dp[i + dist] = dp[i] + diff
print(dp[N - 1])  # 最後の足場にいるときの最小値を出力する
```


## 3 - 部分和問題 - 合計値の最小化

**問題**：[ABC204 D - Cooking](https://atcoder.jp/contests/abc204/tasks/abc204_d)

**N品**の料理をオーブンで作ろうとしており、それぞれのオーブン利用時間は**T**という配列に格納されています。
オーブンは2つだけです。
すべての料理を作り終わるのにかかる時間は何秒かという問題です。

仮にオーブンが1台であれば、**Tの総和**が解答となります。
今回はオーブンが2台のため、解答は**Tの総和/2以上**となります。片方のオーブンの使用時間を短くすればするほどにもう片方のオーブンの使用時間は長くなりますので。

また、片方のオーブンでの料理時間を**A**とするならば、もう片方のオーブンを使う時間は**Tの総和 - A**となるため、片方のオーブンでの料理時間だけを求めれば自ずと全料理の完成時間が求められます。「**A**」と「**Tの総和 - A**」の大きい方が全料理の完成時間です。

つまりは、全組み合わせのうちで**Tの総和/2以上での最小値**を求めればよいとなります。

たとえば料理が2つのときを考えます。
それぞれが**10秒**と**20秒**であるならば、1番目の料理までの組み合わせは**0秒**(Aを作らない)と**10秒**(Aを作る)の2つのみです。

2番目の料理までの組み合わせとなると、**0秒**と**10秒**に対して**20秒**を足すか足さないかの組み合わせなので合計4パターンで**0秒**、**10秒**、**20秒**、**30秒**となります。

合計料理時間は**30秒**ですので**15秒以上**での最小値が解答となります。つまり**20秒**です。

これをコードにしてみます。
今回は **dp[N][Tの総和 + 1]** という配列を用意します。
1次元目は**i番目(0〜)までの料理の組み合わせにおいて**を意味し、2次元目は**合計料理時間をこの秒数にできるか**を意味します。

```Python
import math
N = int(input())
T = list(map(int, input().split()))
total = sum(T)  # Tの合計値

# 配列を用意する
dp = [[False] * (total + 1) for i in range(N)]
dp[0][0] = True  # 0番目の料理を作らない時
dp[0][T[0]] = True  # 0番目の料理を作った時

# 1番目の料理から最後の料理までをループする
for i in range(1, N):
    for j in range(total):
        if dp[i - 1][j]:  # i-1番目の料理まででとりうる料理時間に対して
            dp[i][j] = True  # i番目の料理を作らない時
            dp[i][j + T[i]] = True  # i番目の料理を作る時

# total/2以上の最小値を求める
for i in range(math.ceil(total / 2), total + 1):
    if dp[N - 1][i]:
        print(i)
        exit()
```

## 4 - 最適化問題

問題：[Educational DP Contest / DP まとめコンテスト D - Knapsack 1](https://atcoder.jp/contests/dp/tasks/dp_d)

重さ**w**と価値**v**が割り当てられた**N個**の品物があります。
許容重量が**W**のナップサックに価値が最大化するように品物を入れてくださいという問題です。

いわゆる[ナップサック問題](https://ja.wikipedia.org/wiki/%E3%83%8A%E3%83%83%E3%83%97%E3%82%B5%E3%83%83%E3%82%AF%E5%95%8F%E9%A1%8C)というやつですね。

これも二次元の配列を用意して解くことができます。

**dp[N+1][W+1]** の配列を用意します。
たとえば **dp[3][2]** ならば**3番目の品物までで許容重量が2までの価値の最大値**を示します。

コードにすると下記です。

```Python
N, W = map(int, input().split())
v = [0] * N
w = [0] * N
for i in range(N):
    w[i], v[i] = map(int, input().split())

# 2次元配列を初期値0で用意する
dp = [[0 for i in range(W + 1)] for j in range(N + 1)]

for i in range(N):  # N個の荷物を順番に見る
    for j in range(W + 1):  # ナップサックの許容重量を0〜Wと仮定する
        if w[i] <= j:  # i番目の品物がナップサックの許容重量以下である
            # ナップサックに入れた方が価値が上がるかどうかを求める
            dp[i + 1][j] = max(dp[i][j - w[i]] + v[i], dp[i][j])
        else:  # ナップサックに入れられないのでi-1番目の品物までの時の価値をそのまま用いる
            dp[i + 1][j] = dp[i][j]

print(dp[N][W])
```

## 5 - 2次元最適化問題

問題：[第11回アルゴリズム実技検定 H - 2つのナップサック](https://atcoder.jp/contests/past202206-open/tasks/past202206_h)

ナップサックが**2つ**になったケースです。

**dp**を3次元配列としてます。
**2つ**のナップサックの許容重量を**A**と**B**とすると **dp[N+1][A+1][B+1]** です。

コードは以下です。

```Python
N, A, B = map(int, input().split())

w = [0] * N
v = [0] * N
for i in range(0, N):
    w[i], v[i] = map(int, input().split())

# 3次元配列を初期値0で用意する
dp = [[[0 for k in range(B + 1)] for j in range(A + 1)] for i in range(N + 1)]

for i in range(N):
    for w1 in range(A + 1):  # 1つ目のナップサックの許容重量
        for w2 in range(B + 1):  # 2つ目のナップサックの許容重量
            # i番目のお菓子をいずれかのナップサックに入れられるか判定する
            if w[i] <= w1 or w[i] <= w2:
                # 1つ目のナップサックに入れられる
                if w[i] <= w1:
                    dp[i + 1][w1][w2] = max(dp[i][w1 - w[i]][w2] + v[i], dp[i][w1][w2])

                # 2つ目のナップサックに入れられる
                # 1つ目のナップサックに入れられたケースを考慮してdp[i + 1][w1][w2]もmaxの引数に追加する
                if w[i] <= w2:
                    dp[i + 1][w1][w2] = max(dp[i][w1][w2 - w[i]] + v[i], dp[i][w1][w2], dp[i + 1][w1][w2])

            # ナップサックに入れられないのでi-1番目格納時点の美味しさのままとする
            else:
                dp[i + 1][w1][w2] = dp[i][w1][w2]

print(dp[N][A][B])
```

## 最後に

こういうのがさくっと頭から出てくるようになりたい。

## 宣伝

[SupershipのQiita Organization](https://qiita.com/organizations/supership-inc)を合わせてご覧いただけますと嬉しいです。他のメンバーの記事も多数あります。

Supershipではプロダクト開発やサービス開発に関わる方を絶賛募集しております。
興味がある方は[Supership株式会社 採用サイト](https://supership.jp/recruit/)よりご確認ください。