paizaラーニング問題集「部分和問題 1」を解いてみた（処理の流れの解説あり）

▼考え方

ポイントとなると思った考え方を、以下1.～3.に示します。
これらを踏まえて処理した結果、dp[x(=19)]に1が入力された場合、
yesとなります。

1.　入力xが19かつ、19に対して減算を行う↓
　　(演算のたびにリストの添え字に合わせるため-1するのは面倒なので)
　　dp = [0]*(20)を用意します。

2.　おもりiの重さの値a_iと同じdpの添え字に、1を入力します。
　　例：a_0が7なので、dp[7]←1

3.　a_iとa_i以外を加算した結果と同じdpの添え字に、1を入力します。
　　(ただしx(=19)を超えない範囲)
　　例：a_0が7(dp[7]==1)、a_1が18(dp[18]==1)の状態で
　　　　a_2が5なので、dp[12(=a_0+a_2)]←1

▼コード

########## 処理0(準備) インプット,リスト定義など ###########

n,x = map(int,input().split())
a = [0]*n

########## 処理1 漸化式の定義、計算、出力 ##########

# 考え方1参照
dp = [0]*(x+1)
dp[0] = 1

for i in range(n):
    a[i] = int(input())

# 考え方2,3参照
for i in range(1,n+1):
    for j in range(x,a[i-1]-1,-1):
        if dp[j-a[i-1]] == 1:
            dp[j] = 1

if dp[x] == 1:
    print("yes")
else:
    print("no")

▼処理の流れの解説