[Python] [Explanation] AtCoder Typical DP Contest: A Contest

Link to problem: https://atcoder.jp/contests/tdpc/tasks/tdpc_contest

Introduction

AtCoder version! Arimoto (Beginner) introduced this issue, but there was no official explanation, probably because of an old contest.

I couldn't solve it myself, so I AC while watching the explanation of this article. I'll put my code here for reference. (Because DP is studying, accuracy cannot be guaranteed)

I've added a lot of comments to make it easier to understand.

Implementation

#Receiving input
N = int(input())
P = list(map(int, input().split()))

#Is it possible to get a total of j points using the questions up to the i-question (bool value)?
DP = []
#The 0th question is assumed to be in a state where no problem has been solved. There are N questions, so DP[N]Need up to
for i in range(N+1):
    # N=If 100 and all P's are 100 points
    #The maximum value of the total is 100*100 points (the size of the array is 100 because it may be 0 points)*100+1）
    a = [False] * (100 * 101)
    DP.append(a)

#Using the questions up to the 0th question (=You can get 0 points (do not solve any problem).
#In addition, since it will not be a score other than that, DP[0][0]DP other than[0]The value of the array of is False.
DP[0][0] = True

#Loop from 1st question to Nth question
for i in range(1, N+1):
    # DP[i]DP to put the value in[i-1]I will look at the state of
    for j, dpj in enumerate(DP[i-1]):
        if dpj is True:
            #Do not solve the i-question problem
            DP[i][j] = True

            #Solve the i-question problem
            #The score of the i question is P[i-1]Represented by
            DP[i][j+P[i-1]] = True

ans = 0
# DP[N]Looking at the array of, the total score that can be True
for dpi in DP[N]:
    if dpi is True:
        ans += 1
print(ans)

Concrete example

I think it is difficult to get an image just by implementing it, so let's take a look at the contents of the DP array using "Sample Input 1" as an example.

Sample_Input_1

#input
3
2 3 5

#output
７

Below is the contents of the DP sequence. It means "Can I get j points when I finish solving the i-th question?" From the sample input, the maximum value of j is 10 (2 + 3 + 5).

When i = 0, that is, when the problem is not solved, the only possible score is 0. (Only DP [0] [0] is True) When i = 1, that is, when you finish solving only the first question, the possible score is 0 or 2. (The score of the first question is 2 points) When i = 2, the possible points are 0 points, 2 points, 3 points, and 5 points. (Since the score of the second question is 3 points, add 3 points to the score that is True at i = 1 or not) When such an operation is performed up to i = 3, True is "0, 2, 3, 5, 7, 8, 10", so the answer is 7.

that's all.