9084コインG 5

https://www.acmicpc.net/problem/9084
ただいきなりリュック問題に陥り、簡単なことから試してみました.
この問題は前に解いた問題よりもっと考えなければならない.
テーブルは同じように生成されます.(コインの個数)*(作成金額+1)大きさのテーブルが必要です.さらに考えなければならない部分は、同じコインを何度も使うことができることです.言い換えれば、1元、5元、10元はそれぞれ無限個を与え、100元を求める方法の数は、前に解答した本当の基本的なリュックサック問題の中で一つのものだけを与える方法とは少し違います.
そこで,dpテーブルの意味を再確認し,解決策を考えた.
まずdp[i][j]は0番目のコインから始まり、i番目のコインを使ってj円を作ります.
従来のバックパック問題では、iの第1の物品をjに含めることができれば、dp[i-1][j]とdp[i-1][j-(iの第1の物品の重量)]+iの第2の物品の価値の値とを比較してより大きな値を格納し、含めることができなければdp[i-1][j]の値を使用している.
しかし、ここではずっと言っていたようにはできません.上の1、5、10元の例を取って、30元が1元と5元で作られていると思ったら、dpテーブルの1行目は1で埋められ、2行目を埋めているはずです.dp[1][30]の位置の値はdp[0][30](一元で30元)、dp[0][25](一元で25元)、dp[0][20](一元で20元)です.dp[0][0](1元で0元にすると)全部加算します.
なぜなら...1元で30元作ったら5元はいらないし、25元作ったら5元を1つ入れるだけでいいです.20元なら5元の2つ.(繰り返し)
次の行まで、10元まで使います.dp[2][30]の値が知りたいです.
結論から言えば、dp[1][30]+dp[1]+20]+dp[1][10]+dp[1][0].

dp[1][30]:1元と5元で30元を作る方法数

dp[1][20]:1元と5元で20元を作る方法数

dp[1][10]:1元と5元で10元を作る方法数

dp[1][0]:1元と5元で0元を作る方法数

それぞれの方法の数を加算すればいいです.dp[1][20]は最終的に1個10元を使うことに等しく、残りは1元と5元で30元を作る.残りも同じです.dp[1][0]は3個10元で、残りは1元と5元で記入されているので、1のはずです.
文字で書くのは少し乱れているように見えますが、コードで整理するのはずっと簡単です.
コインは1元から10000元で、作った金額も1元から10000元です.
いずれにしても、もう一度複文をつけるべきなので、いろいろな範囲を減らしました.

from sys import stdin

test = int(stdin.readline())
for t in range(test):
    n = int(stdin.readline())
    coins = list(map(int, stdin.readline().split()))
    m = int(stdin.readline())
    
    dp = [[0 for i in range(m + 1)] for j in range(n)]
    
    for i in range(n):
        for j in range(m + 1):
            if i == 0: # 첫 번째 줄 처리
                if j % coins[i] == 0:
                    dp[i][j] = 1
                else:
                    dp[i][j] = 0
            else:
                for k in range(j, -1, -coins[i]):
                    dp[i][j] += dp[i-1][k]
    
    print(dp[-1][-1])