2022/06/29 ABC240C

ABC240 C - Jumping Takahashi

atcoder.jp

DPの考え方が定着しない． 最初DPもどきなコードを書いてしまった．

N, X = list(map(int,input().split()))
dp = [set() for i in range(N+1)]

dp[0].add(0)
for i in range(N):
    a, b = list(map(int, input().split()))
    l = list(dp[i])
    for j in range(len(l)):
        dp[i+1].add(l[j]+a)
        dp[i+1].add(l[j]+b)
if X in dp[N]:
    print("Yes")
else:
    print("No")

想定解とはちょっと違う解き方をしてしまったので，解説を読みながら解きなおした． 配列の要素に何を入れればいいのかがイメージできないから，DPをいつまで経っても書けないんだろうな．

N, X = list(map(int,input().split()))
# dp[i][j]:i回ジャンプを行った時点で座標jの位置にいることが可能なら1,不可能なら0
dp = [[0]*(X+1) for i in range(N+1)]
dp[0][0] = 1
for i in range(N):
    a, b = list(map(int,input().split()))
    for j in range(X):
        if dp[i][j] == 1:
            if j+a <= X:
                dp[i+1][j+a] = 1
            if j+b <= X:
                dp[i+1][j+b] = 1

if dp[N][X] == 1:
    print("Yes")
else:
    print("No")