[Python][解説]AtCoder Typical DP Contest：A コンテスト #Python

問題へのリンク：https://atcoder.jp/contests/tdpc/tasks/tdpc_contest

はじめに

AtCoder 版！蟻本 (初級編）にこの問題が紹介されていましたが、古いコンテストのためか公式の解説がありませんでした。

自分では解けず、こちらの記事の解説を見ながらACしました。参考までに自分のコードを載せておきます。（DPは勉強中のため、正確性は保証できません）

わかりやすいように、コメントをたくさん付けました。

実装

# 入力の受け取り
N = int(input())
P = list(map(int, input().split()))

# i問目までの問題を使って、j点の合計点ができるか（bool値）
DP = []
# 0問目は1問も問題を解いていない状態とする。N問あるので、DP[N]まで必要
for i in range(N+1):
    # N=100かつすべてのPが100点だった場合、
    # 合計の最大値は100*100点になる（0点の場合もあるので配列のサイズは100*100+1）
    a = [False] * (100 * 101)
    DP.append(a)

# 0問目までの問題を使って（=問題を一問も解かない）0点を取ることができる。
# また、それ以外の点数にはならないため、DP[0][0]以外のDP[0]の配列の値はFalseになる。
DP[0][0] = True

# 1問目からN問目までのループ
for i in range(1, N+1):
    # DP[i]に値を入れていくために、DP[i-1]の状態を見ていく
    for j, dpj in enumerate(DP[i-1]):
        if dpj is True:
            # i問目の問題を解かない
            DP[i][j] = True

            # i問目の問題を解く
            # i問目の得点はP[i-1]で表される
            DP[i][j+P[i-1]] = True

ans = 0
# DP[N]の配列を見て、Trueになっているところがありうる合計点
for dpi in DP[N]:
    if dpi is True:
        ans += 1
print(ans)

具体例

実装だけではイメージがつきにくいと思うので、「Sample Input 1」を例にDP配列の中身を見てみましょう。

Sample_Input_1

# 入力
3
2 3 5

# 出力
７

下記はDP配列の中身です。「i問目まで解き終えたときにj点になることがあるか」を表しています。
サンプルの入力よりjの最大値は10（2+3+5）になります。

i\j	0	2	3	5	7	8	10
0	1	0	0	0	0	0	0
1	1	1	0	0	0	0	0
2	1	1	1	1	0	0	0
3	1	1	1	1	1	1	1

i=0のとき、すなわち問題を解いていないときに、ありうる得点は0だけです。（DP[0][0]のみがTrue）
i=1のとき、すなわち１問目の問題のみを解き終えたとき、ありうる得点は、0点か2点です。（1問目の得点は2点です）
i=2のとき、ありうる得点は、0点、2点、3点、5点です。（２問目の得点は3点なので、i=1でTrueとなっている得点に3点を足すか、足さないか）
このような操作をi=3まで行ったとき、Trueとなるのは「0, 2, 3, 5, 7, 8, 10」ですので、答えは7になります。

以上です。