2変数の動的計画法

/

2変数の動的計画法について

タグ

概要

2変数a,bのパラメータを持つ要素eがある。Eの組み合わせでa,bの累計A,Bが特定の値を超える最小の個数を求める

考え方

dp[aの値][bの値] = 個数のベクトルを考える

繰り返しのないdpを考える。繰り返しのないdpは逆順に当てはめていけば繰り返さない

コード例

N = int(input())
X, Y = map(int, input().split())

AB = []
for n in range(N):
    AB.append(list(map(int, input().split())))

INF = float("inf")
dp = [[INF]*(Y+1) for x in range(X+1)]
dp[0][0] = 0

for a, b in AB:
    for i in range(X+1)[::-1]:
        for j in range(Y+1)[::-1]:
            if dp[i][j] != INF:
                dp[min(X, i+a)][min(Y, j+b)] = min(dp[min(X, i+a)][min(Y, j+b)], dp[i][j]+1)
# check over
# ans = min([min(x[Y:]) for x in dp[X:]])
ans = dp[X][Y]
if ans == INF:
    print(-1)
else:
    print(ans)