dynamic programming

date: 2018-01-01 excerpt: 動的計画法について

tag: algorithm dynamic programming

動的計画法について

概要

具体例を例示しつつ説明する
多くの解決法として、listやvectorを作成し、0 or inf等を入力し、前の入力から今の入力の最小や最大を取得する
適応例
- 全組み合わせせの探索としても使る
  - その場合二次元マトリックスを作成する
- 手順を踏んで計算するとO(n^3)やO(n^2)の計算になってしまうような場合
  - 小さいサンプルから一般化すると動的計画法で得られるように導くことができる
- シミュレーションとしてdpの構造を利用することもできる
pythonでやる際
- リストのリストのアクセスが遅いので、リストのリストを作らずに、一つのリストを更新していく方法でも解ける

例; 繰り返しのないナップサック問題

問題

DPL_1_B

解答

N, W = map(int, input().split())

VW = []
for n in range(N):
    v, w = map(int, input().split())
    VW.append((v, w))

dp = [[0]*(W+10) for _ in range(N+1)]
for i, (v, w) in enumerate(VW):
    for j in range(0, W+10):
        if j >= w:
            dp[i+1][j] = max(dp[i][j], dp[i][j-w] + v)
        else:
            dp[i+1][j] = dp[i][j]
print(dp[-1][W])

例; 繰り返しのあるナップサック問題

問題

DPL_1_A

解答

N,M=map(int,input().split())
A=list(map(int,input().split()))

dp=[float('inf')]*(N+10)
dp[0] = 0
for a in A:
    for j in range(len(dp)):
        if j >= a:
            dp[j] = min(dp[j], dp[j-a] + 1)
print(dp[N])

例; 基礎的な部分和問題

問題

Typical DP Contest; A - コンテスト

解答1

N=int(input())
A=list(map(int,input().split()))

POINTS_MAX = 100*100 + 10
dp = [[0]*POINTS_MAX for _ in range(len(A)+1)]
dp[0][0] = 1
for i in range(len(A)):
    for j in range(POINTS_MAX):
        dp[i+1][j] |= dp[i][j] # 上の状態と同じ
        if j >= A[i]: # itemを選択できるならば
            dp[i+1][j] |= dp[i][j-A[i]] # 前のアイテムが有るならばtrueになる(アイテムがtrueをフォワードできる)
print(sum(dp[len(A)]))

解答2

N=int(input())
*P,=map(int,input().split())

dp = [[0]*(sum(P) + 10) for _ in range(N+1)]
dp[0][0] = 1
for i in range(N):
    for j in range(sum(P)+10):
        dp[i+1][j] = dp[i][j]
        if j - P[i] >= 0:
            dp[i+1][j] += dp[i][j-P[i]]
print(len(list(filter(lambda x:x>0,dp[-1]))))

例; 最小個数部分和問題

問題

n個の正の整数 a[0],a[1],…,a[n−1]a[0],a[1],…,a[n−1] と正の整数 AA が与えられる。
これらの整数から何個かの整数を選んで総和が AA にする方法をすべて考えた時、選ぶ整数の個数の最小値を求めよ。Aにすることができない場合は -1 と出力せよ。

解答

N=5
I=[7,5,3,1,8]
A=12
dp = [[float("inf")] * (A+2) for _ in range(N+1)]
dp[0][0] = 0
for i in range(len(I)):
    for j in range(A+1):
        if j >= I[i]:
            dp[i+1][j] = min(dp[i][j - I[i]] + 1, dp[i][j])
        else:
            dp[i+1][j] = dp[i][j]
print(dp[-1][A])

例; 階段の動きをdpを用いてシミュレーションする

問題

AtCoder Beginner Contest 129; C - Typical Stairs

解答

N, M = map(int,input().split())
MOD = 10**9 + 7
A = [int(input()) for _ in range(M)]
A = set(A)

dp = [0]*(N+2)
dp[0] = 1

for i in range(len(dp)):
    if i+2 not in A:
        if i+2 <= N:
            dp[i+2] += dp[i]
            dp[i+2] %= MOD

    if i+1 not in A:
        if i+1 <= N:
            dp[i+1] += dp[i]
            dp[i+1] %= MOD

print(dp[N]%MOD)

例; dpの更新式の中に任意の操作を組み込む

問題

AtCoder Beginner Contest 099; C - Strange Bank

解答

N=int(input())

dp = [float("inf")] * (N+100)
dp[0] = 0

for i in range(N):
    if i+1 < len(dp):
        dp[i+1] = min(dp[i+1], dp[i]+1)

    r = 6
    while True:
        if i+r < len(dp):
            dp[i+r] = min(dp[i+r], dp[i]+1)
        else:
            break
        r *= 6

    r = 9
    while True:
        if i+r < len(dp):
            dp[i+r] = min(dp[i+r], dp[i]+1)
        else:
            break
        r *= 9
print(dp[N])

例; 9の倍数の各桁の和を取るとKになる。Kになる通りは何通りか

問題

競プロ典型 90 問; 042 - Multiple of 9 解説
なかなかこのdpは発想ができないのでテンプレ化する必要がありそう解答

MOD = 10**9 + 7

K = int(input())

if K%9 != 0:
    print(0)
    exit()

dp = [0] * (K+1)
dp[0] = 1
for i in range(len(dp)):
    b = min(i, 9)
    for j in range(1, b+1):
        dp[i] += dp[i-j]
        dp[i] %= MOD

print(dp[K])

例; まともに計算するとO(n^3)になるのをO(n)に変換する

問題

京セラプログラミングコンテスト2021; E - Patisserie ABC 2

解説
小さいサンプルで試すと、インプットが大きいほうが長い配列になることが確認できる
配列の作成され方にも法則性がありそうである
法則性は動的計画法で作成可能である(非常に定式化が難しい例)

公式解説

解答

提出
colab

例; 中間的な最適解を与えながら計算する

問題

AtCoder Beginner Contest 197; E - Traveler

解説
中間的な最適解が色を選ぶたびに得られる
この中間的な最適解を次のステップの最適解を構築する

解答

colab

例; Money Change Again

問題

解説

前の入力から最もコイン数が小さいものを選択する

解答

import math

money = int(input())
denominations = [1, 3, 4]
minCoins = [0] + [math.inf]*money
for i in range(1, money+1):
    for j in denominations:
        if i>=j:
            coins = minCoins[i-j]+1
            if coins < minCoins[i]:
                minCoins[i] = coins
print(minCoins[money])

例; Primitive Calculator

問題

解説

入力された値が最小何回の電卓の操作で達成できるか
前の状態で場合分けを行う(もらうdp)
backtraceが難しい

解答

N = int(input())

"""最小の操作回数を求めるdp"""
dp = [0, 0] + [float("inf")]*(N-1)
for i in range(2, N+1):
    tmp1, tmp2, tmp3 = [(float("inf"), "none")]*3
    tmp1 = (dp[i-1] + 1, "add")
    if i%2 == 0:
        tmp2 = (dp[i//2] + 1, "mul2")
    if i%3 == 0:
        tmp3 = (dp[i//3] + 1, "mul3")
    min_ops, op = min(tmp1, tmp2, tmp3)
    dp[i] = min_ops
print(dp[N])

"""逆順から見ていき、操作を再現する"""
nums = [N]
while N!=1:
    if N%3 ==0 and dp[N]-1 == dp[N//3]:
        nums += [N//3]
        N = N//3
    elif N%2 ==0 and dp[N]-1 == dp[N//2]:
        nums += [N//2]
        N = N//2
    else:
        nums +=[N-1]
        N = N - 1
print(*nums[::-1])

例; “+”, “-“の組み合わせで表現される数のパターンはいくつあるか

問題

AtCoder Regular Contest 122; A - Many Formulae

解説

少ないデータではpermutationやdfsで全探索できるが10^5オーダーなので全探索は無理
dpで状態を作っていくことになるが、その利用が大変むずかしい
- ある点までの”+”, “-“の組み合わせ数は最終的に得られる”+”, “-“に一致しない
- dp[1][i - 1] * dp[1][N - 1 - i] + dp[0][i - 1] * dp[1][N - 1 - i] + dp[1][i - 1] * dp[0][N - 1 - i]で得られる

解答

""" MODINTを省略 """ 
import sys; sys.setrecursionlimit(10**9)
import collections
N=int(input())
*A,=map(int,input().split())
MOD = 10**9 + 7
dp[0][0] = 1
dp[1][0] = 0
for i in range(1, N):
    # + -> +
    dp[0][i] += dp[0][i - 1]
    # - -> +
    dp[0][i] += dp[1][i - 1]
    dp[0][i] %= MOD
    # + -> -
    dp[1][i] += dp[0][i - 1]
    dp[1][i] %= MOD

# print(*dp, sep="\n")
"""ここまでは簡単"""

ans = Mint(A[0])
ans *= (dp[0][N - 1] + dp[1][N - 1])
for i in range(1, N):
    t = Mint(0)
    """ここが難しい"""
    t += dp[1][i - 1] * dp[1][N - 1 - i]
    t += dp[0][i - 1] * dp[1][N - 1 - i]
    t += dp[1][i - 1] * dp[0][N - 1 - i]
    ans += A[i] * t
print(ans)

提出

例; 区間(範囲)を定義された特定の移動方があるとき、目的地につくまで移動法は何通りあるか

問題

AtCoder Beginner Contest 179; D - Leaping Tak

解説

最初を1としたテーブルを作成し、そこから何通りあるかを考える
累積和の考え方を持ち込み、dpの累積和を計算しつつ、r+1以降を消していく

解答

N,K = map(int,input().split())

MOD = 998244353
LR = []
for k in range(K):
    L,R = map(int,input().split())
    LR.append((L,R+1))

dp = [0]*(N+1)
dp[0] = 1
dp[1] = -1
for i in range(N):
    if i > 0:
        dp[i] += dp[i-1]
    for l, r in LR:
        if i + l < N:
            dp[i+l] += dp[i]
            dp[i+l] %= MOD
        if i + r < N:
            dp[i+r] -= dp[i]

print(dp[N-1] % MOD)

例; 典型的な最小コストを求めるdp(厳密に求まらない例)

問題

AtCoder Beginner Contest 153; E - Crested Ibis vs Monster

解説

厳密にほしい大きさKがinfになり求まらない例
K以上に出現する初めてのinfより小さい値が解になる

解答

H,N=map(int,input().split())

dp = [float("inf")]*(2*(10**4))
dp[0] = 0

AB = []
for _ in range(N):
    a,b =map(int,input().split())
    AB.append( (a,b) )

for a, b in AB:
    for i in range(len(dp)):
        if i >= a:
            dp[i] = min(dp[i-a]+b, dp[i])

print(min(dp[H:]))

例; 復元があるdp(たどった変遷を記録するdp)

問題

競プロ典型 90 問; 056 - Lucky Bag

解説

通常のdpに近いが、各アイテムが２つ選択肢を持つという点がユニーク
dpの配列の中に前の参照を入れておくことで、どの経路で答えが得られたかをたどることができる

解答

N,S=map(int,input().split())

AB = []
for _ in range(N):
    a,b=map(int,input().split())
    AB.append( (a,b) )

dp = [[0]*(S+1) for _ in range(N+1)]
dp[0][0] = (1, "S")

for i in range(N):
    for j in range(S+1):
        if j - AB[i][0] >= 0:
            if dp[i][j - AB[i][0]] != 0:
                dp[i+1][j] = (j-AB[i][0], "A")
        if j - AB[i][1] >= 0:
            if dp[i][j - AB[i][1]] != 0:
                dp[i+1][j] = (j-AB[i][1], "B")

if dp[-1][S] == 0:
    print("Impossible")
    exit()

ans = []
icur = N
a = dp[icur][S]
scur = a[0]
ans.append(a[1])
while True:
    icur -= 1
    a = dp[icur][scur]
    if a[1] == "S":
        break
    ans.append(a[1])
    scur = a[0]
print("".join(ans[::-1]))

例; 動きをdpテーブルに記していき、パターン数をカウントする方法

問題

三井住友信託銀行プログラミングコンテスト2019; E - Colorful Hats 2

考察

一番、被られている防止の個数を必ず一番上にする
順序がある場合、dpのテーブルのようにできるから、個数をカウントする
帽子をおける候補が２つ以上ある場合、その分だけ、パターン数を倍数する

解答

N = int(input())
*A, = map(int, input().split())
MOD = 10**9 + 7
ans = 1

s = [0, 0, 0]
for n in range(N):
    ans *= s.count(A[n])
    if ans == 0:
        break
    ans %= MOD
    s[s.index(A[n])] += 1
print(ans)