AtCoder Beginner Contest 153 E - Crested Ibis vs Monster【Python】

AtCoder

https://atcoder.jp/contests/abc153/tasks/abc153_e

AtCoder ProblemsでDifficulty: 1015、Solve Probability: 19%でした。

ちょうどアルゴ式でDPについて勉強したところだったため問題文を見てDPで解けそうという検討がつきました。

algo-method.com

H, N = map(int, input().split())
A = []
B = []
for i in range(N):
    a, b = map(int, input().split())
    A.append(a)
    B.append(b)
maxA = max(A)
dp = [[INF] * (H + 1 + maxA) for _ in range(N + 1)]
dp[0][0] = 0
for i in range(N):
    for j in range(H + 1 + maxA):
        if j - A[i] >= 0:
            dp[i + 1][j] = min(dp[i][j - A[i]] + B[i], dp[i + 1][j])
            # 同じ魔法を何度も使う場合
            dp[i + 1][j] = min(dp[i + 1][j - A[i]] + B[i], dp[i + 1][j])
        dp[i + 1][j] = min(dp[i + 1][j], dp[i][j])

print(min(dp[N][H:]))