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)