Atcoder Typical DP contest A問題 - moratoriumer’s diary

今年は少し競プロを頑張りたいので、DPの練習をすることにした。
人に説明すると自分の理解が深まる気がするので方針と実装をダサくても積極的に晒して行きたい。
Typical DP Contest - AtCoder

問題

解法

i個の問題を解いた時、配点の合計がjとなりうる場合は1、どのように解いてもjとならない場合は0を取る関数を $dp(i, j)$ と書くことにする。
定義域は $0\leq i\leq N$ 、 $0\leq j \leq \sum_{i} p_{i}$
$dp(i, j)$ を0または1の値に取るようにしたのは、最終的に

$\sum_{j}dp(N, j) =$ N問解いた時の配点の得点の場合の数

として、配点の場合の数を数え上げたいからである。

i個の問題を解いた時、配点の合計がjとなる場合は、
①i-1個の問題を解いた段階で配点の合計がjとなっていて、i番目の問題は解かない
②i-1個の問題を解いた段階で配点の合計が $j-p[i]$ となっていて、i番目の問題(配点は $p[i$ ])を解く
の二通りがある。よって解くべき漸化式は以下のようになる。

$dp(i, j) = max(dp(i-1, j), dp(i-1, j-p[i]))$ $(j\geq p[i])$
$dp(i, j) = dp(i-1, j)$ $(j < p[i])$

すなわち、 $dp(i-1, j)=1$ または $dp(i-1, j-p[i])=1$ が成り立てば、 $dp(i, j)=1$ となり、 $dp(i-1, j)=0$ かつ $dp(i-1, j-p[i])=0$ の時のみ、 $dp(i, j)=0$ となるような漸化式を立てた。

初期条件は
$dp(0, 0) = 1$
$dp(1, j) = 0$ ( $1\leq j \leq N$ )
配点が0の場合も1通りとして数えることに注意する。

実装

あとは上の漸化式を実装する。メモ化再帰でしか書けない脳みそなのでメモ化再帰で書く。
実装言語:Python 3.6.1

N = int(input())
p = list(map(int, input().split()))

sum_p = sum(p)
#prepare memo
memo = [[-1 for _ in range(sum_p+1)] for _ in range(N+1)]

#set initial condition
memo[0][0] = 1
for i in range(1, sum_p+1):
    memo[0][i] = 0

#define dp function
def dp(i, j):
    global memo, p
    if memo[i][j] == -1:
        if j>=p[i-1]:
            memo[i][j] = max(dp(i-1, j), dp(i-1, j-p[i-1]))
        else:
            memo[i][j] = dp(i-1, j)

    return memo[i][j]

#calculate dp
for j in range(sum_p+1):
    dp(N, j)

print(sum(memo[N]))