動的計画法をおさらいした

AtCoderのABC問題の解説を見ていたらBitDPを使う問題が出てきたのだが、
解説を見てもよくわからんので、動的計画法を基礎からやり直すことにした。
入門的な問題～ナップサック問題までPythonで実装したので記録しておく。
BitDPまでやろうと思ったのだがナップサック問題までで結構な量になってしまったのでそれはまたいつか。

1. Frog 1

問題文

N個の足場があります。足場には1, 2, …, Nと番号が振られています。
各i (1 ≤ i ≤ N)について、足場iの高さはhiです。
最初、足場1にカエルがいます。
カエルは次の行動を何回か繰り返し、足場Nまで辿り着こうとしています。

足場iにいるとき、足場i + 1またはi + 2へジャンプする。
このとき、ジャンプ先の足場をjとすると、コスト | hi − hj |を支払う。

カエルが足場Nに辿り着くまでに支払うコストの総和の最小値を求めてください。

制約

入力はすべて整数である。
2 ≤ N ≤ 10⁵
1 ≤ hi ≤ 10⁴

考え方

例としてn = 7、h = [2, 9, 4, 5, 1, 6, 10]の場合を考える。
問題文では足場の番号は1オリジンだが、配列のインデックスと合わせるため0オリジンで考える。
ここで、DP値を格納する配列dp を用意し、
dp[i]を、「i番目の足場に到達するためのコストの最小値」と定義する。

i = 0の場合

dp[0]は「0番目の足場に到達するためのコストの最小値」ということになる。
0番目の足場はスタート地点なので、辿り着くコストは0。
したがってdp[0] = 0 となる。

i	0	1	2	3	4	5	6
dp[i]	0

i = 1の場合

1番目の足場にたどり着くには、

0番目の足場からジャンプしてくる

1通りの方法しか存在しない。
したがって dp[1] = | h0 − h1 | = | 2 − 9 | = 7 となる。

i	0	1	2	3	4	5	6
dp[i]	0	7

i = 2の場合

2番目の足場にたどり着くには、

0番目の足場からジャンプしてくる
1番目の足場からジャンプしてくる

2通りの方法が存在する。
したがって dp[2]は | h0 − h1 | か | h0 − h2 |のうち小さい方となる。
この例では、| h0 − h2 | = 2 が最小。

i	0	1	2	3	4	5	6
dp[i]	0	7	2

最終結果

この繰り返しで、ゴールであるi = 6までを埋めたものが以下。

i	0	1	2	3	4	5	6
dp[i]	0	7	2	3	5	4	8

dp[6] = 8 は 6番目の足場に到達するためのコストの最小値 なので、答えは8。
このように、部分問題の計算結果を記録しながら最終的な答えを求めるアルゴリズムを「動的計画法」という。

実装

以下のように、DPテーブルの設定→初期化→初期条件→ループ→最終的な答えの出力というステップを踏むケースが多い。
最大値を求める場合は十分に小さい定数で、最小値を求める場合は十分に大きい定数で初期化する。
配列のindexと問題分の番号を混同しないように注意する。

# 柱の本数
n = 7
# 柱の高さ
h = [2, 9, 4, 5, 1, 6, 10]
# DPテーブル初期化値
INF = 1000000
# DPテーブル (dp[i]：i番目の柱に到達するためのコストの最小値)
dp = [INF for i in range(n)]

# 0番目の柱に到達するためのコストは0
dp[0] = 0

# dp[1]～dp[n-1]までループ
for i in range(1, n):
    # i = 1の場合、0番目の柱から1つ飛びで来るパターンしかない
    if (i <= 1):
        dp[i] = dp[i - 1] + abs(h[i - 1] - h[i])
    # それ以外の場合、1つ飛びパターンと2つ飛びパターンのうち小さい方が選ばれる
    else:
        dp[i] = min(dp[i - 1] + abs(h[i - 1] - h[i]),
                    dp[i - 2] + abs(h[i - 2] - h[i]))

# 最終地点のDPテーブルの値が答えとなる
print(dp[n - 1])

2. Typical Stairs

問題文

N段の階段があります。高橋君は現在、上り口(0段目)にいます。
高橋君は一歩で1段か2段上ることができます。
ただし、a1,a2,a3,....aM段目の床は壊れており、その段に足を踏み入れることは危険です。
壊れている床を踏まないようにしながら、最上段(N段目)にたどりつくまでの移動方法は何通りあるでしょうか？
総数を1,000,000,007で割った余りを求めてください。

制約

1 ≤ N ≤ 10⁵
0 ≤ M ≤ N − 1
1 ≤ a1 < a2< ... < aM ≤ N − 1

実装

正答を出すまでにTLEがいっぱい出た。
- 当初は「壊れた階段リスト」を持っていたが、dpを1で初期化して、壊れている階段の箇所にdp値(0)を初期条件として入力し、dp値の更新時に自分の値を係数として掛けることで「壊れた階段リスト」を使わないようにした。
- list.append() は極力使わないようにする。

# DPテーブル初期化値
INIT = 1
n, m = map(int, input().split())
# 初期化
dp = [INIT for i in range(n + 1)]
# 初期条件
for i in range(m):
    a = int(input())
    dp[a] = 0
# dp[2] ~ dp[n]までループ
for i in range(2, n + 1):
    dp[i] = (dp[i - 1] + dp[i - 2]) * dp[i]
 
print(dp[n] % 1000000007)

3. Vacation

問題文

明日から太郎君の夏休みが始まります。
太郎君は夏休みの計画を立てることにしました。
夏休みはN日からなります。
各i(1 ≤ i ≤ N)について、i日目には太郎君は次の活動のうちひとつを選んで行います。

A:海で泳ぐ。幸福度aiを得る。
B:山で虫取りをする。幸福度biを得る。
C:家で宿題をする。幸福度ciを得る。

太郎君は飽き性なので、2日以上連続で同じ活動を行うことはできません。
太郎君が得る幸福度の総和の最大値を求めてください。

制約

入力はすべて整数である。
1 ≤ N ≤ 10⁵
1 ≤ ai, bi, ci ≤ 10⁴

実装

今までのやり方では答えを出すことができない。
- 前日にどの活動を選択していたのかが一次元配列ではわからない
- よってi日目ではどの活動が選択可能なのかがわからない
dp[i][j] = i日目に活動jを選択した場合の幸福度の最大値 というように各活動を選択した場合を考慮する必要がある。
dpに添字を付け拡張することができるかを問う問題。

# 初期値
INF = 1000000
# 休みの日数
n = int(input())
# 満足度テーブル
t = [[int(i) for i in input().split()] for j in range(n)]
# 活動リスト(A = 0, B = 1, C = 2)
a = [0, 1, 2]
# DPテーブル
# dp[i][j]：
# i日目に活動jを選択した場合の幸福度の最大値
dp = [[-INF for i in range(3)] for j in range(n)]

# 初期条件(0日目の各活動の幸福度)
for j in range(3):
    dp[0][j] = t[0][j]

# dp[1][0]～dp[n-1][2]までループ
for i in range(1, n):
    for j in range(3):
        # 活動リストとjの差集合
        # ex) j = 0のときk = [1, 2]をとる
        k = list(set(a).difference(set([j])))
        # i日目の活動jの幸福度と、i-1日目のj以外の活動のうち幸福度が高い方を加算してdp[i][j]とする
        dp[i][j] = max(dp[i - 1][k[0]], dp[i - 1][k[1]]) + t[i][j]

# 最終日のdpテーブルのうち満足度が最大のものが答え
print(max(dp[n - 1][0], dp[n - 1][1], dp[n - 1][2]))

4. Knapsack 1

問題文

N個の品物があります。
品物には1,2,…,Nと番号が振られています。
各i(1 ≤ i ≤ N)について、品物iの重さはwiで、価値はviです。
太郎君は、N個の品物のうちいくつかを選び、ナップサックに入れて持ち帰ることにしました。
ナップサックの容量はWであり、持ち帰る品物の重さの総和はW以下でなければなりません。
太郎君が持ち帰る品物の価値の総和の最大値を求めてください。

制約

入力はすべて整数である。 1 ≤ N ≤ 100
1 ≤ W ≤ 10⁵
1 ≤ wi ≤ W
1 ≤ vi ≤ 10⁹

実装

有名なナップサック問題。
部分和をDPテーブルの添字として利用できるか否かを問う。
難しかった……。0オリジンと1オリジンで頭が割れそうになる。

# 初期値
INIT = 0
# 品物の個数
n = 6
# 重量の上限
W = 15
# 重さリスト
arr_w = [6, 5, 6, 6, 3, 7]
# 価値リスト
arr_v = [5, 6, 4, 6, 5, 2]
# DPテーブル
# dp[i][w]
# i番目までの品物の中から重さwを超えないように選択した場合の価値の最大値
dp = [[INIT for i in range(W + 1)] for j in range(n + 1)]

# 初期条件
# 何も選ばない場合の価値は0
for i in range(W + 1):
    dp[0][i] = 0

# dp[1][0]～dp[n][W]までループ
for i in range(1, n + 1):
    for w in range(W + 1):
        # 品物を選ぶ場合
        if (w >= arr_w[i - 1]):
            dp[i][w] = max((dp[i - 1][w - arr_w[i - 1]] + arr_v[i - 1]),
                           dp[i - 1][w])
        # 品物を選ばない場合
        else:
            dp[i][w] = max(dp[i - 1][w], dp[i][w])

print(dp[i][W])

参考

qiita.com

ごっそログ

勉強したことなどを書いていきます