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

▼考え方

ポイントとなると思った考え方を、以下1.～5.に示します。

1.dpは、ある重さを、おもりの重さa_iやa_i以前のおもりを複数組合わせることで実現できるかどうかを示すリストです。例：a_0は7なのでdp[7]=1、a_1は3なのでdp[3]=1、a_0+a_1で10なのでdp[10]=1

2.dp2は、a_iを何個か選んで重さの和がxとなるようにする方法のうち、選ぶおもりの個数の最小値を示すリストです。例：a_0=7とa_1=3があるときdp2[10]=2、次にa_n=10が現れたときdp2[10]=1と更新します。
　
3.ある重さjが、a_iやa_i以前のおもりを複数組合わせることで実現できるのであれば、dp[j]←1と更新します。

4.ある重さjが、a_iのみで実現できるのであれば、dp2[j]←1と更新します。例：重さ7はa_0=7のみで実現できるのでdp2[7]←1と更新します。

5.ある重さjが、a_iをa_i以前のおもりの組合わせで実現できるのであれば、おもりが少ないほうの組合わせの数でdp2[j]を更新します。（考え方2の実現）

▼コード

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

n,x = map(int,input().split())

a = [0]*n

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

dp = [0]*(x+1)
dp2 = [0]*(x+1)
dp[0] = 1

for i in range(n):

    a[i] = int(input())

for i in range(1,n+1):

    for j in range(x,a[i-1]-1,-1):

        # 考え方3.
        if dp[j-a[i-1]] == 1:
            dp[j] = 1

            # 考え方4.
            if j-a[i-1] == 0:
                dp2[j] = 1
                
            # 考え方5.
            else:
                if dp2[j] == 0 or (dp2[j] > dp2[j-a[i-1]]+1):
                    dp2[j] = dp2[j-a[i-1]] + 1

if dp2[x] == 0:
    print(-1)
else:
    print(dp2[x])

▼考え方5の補足

おもりが少ないほうの組合わせの数だけdp2[j]に保持するのではなく、すべての組合わせの数を保持させるようなコードも作りました。例：a_0=7とa_1=3があるときdp2[10]=2、次にa_n=10が現れたときdp2[10]=(1,2)

しかし実行するとエラーコードにkilledと表示されました。おそらくdp2のために確保するメモリが上限を超えてしまったものと思います。