Atcoder Beginner Contest 153

E

個数なしナップサック問題。
再帰で組んだが、計算量を考慮しておらずTLE。
配列を用いたdpの作り方がわからずタイムアップとなった。

解説はyoutubeにて、
https://www.youtube.com/watch?v=pHzHTVIqrG8&feature=youtu.be

Hitpoint, N = map(int, input().split())
magic_damage = []
magic_point = []
for _ in range(N):
    A, B = map(int, input().split())
    magic_damage.append(A)
    magic_point.append(B)

# dp = [[float("inf") for _ in range(Hitpoint + 1)] for _ in range(N + 1)]
dp = [float('inf') for _ in range(Hitpoint + 1)]
dp[0] = 0
for i in range(N):
    for now_HP in range(Hitpoint + 1):
        next_HP = min(now_HP + magic_damage[i], Hitpoint)
        dp[next_HP] = min(dp[next_HP], dp[now_HP] + magic_point[i])
        
        # dp[i + 1][now_HP] = min(dp[i + 1][now_HP], dp[i][now_HP - magic_damage[i]] + magic_point[i])
print(dp[Hitpoint])