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

▼考え方

ポイントとなると思った考え方を、以下1.～4.に示します。
これらを踏まえて処理した結果、dp[x(=10)]に入力された数が、
重さの和が10となるようにする方法の数です。

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

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

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

4.　a_iとa_i以外を加算した結果が、複数パターンある場合は、
　　それをdpの添え字で表現する。
　　例：a_0が7なので、まずdp[7]←1となる。
　　　　次に、a_1が3でa_2が4なのでこれもdp[7(=a_1+a_2)]←1となる。
　　　　よってdp[7]←2(=1+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,4参照
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] += dp[j-a[i-1]]

print(dp[x] % 1000000007)

▼処理の流れの解説