Typical DP Contest A - コンテスト

問題

atcoder.jp

問題概要

N問の問題があるコンテストがあり、i問目(1-index)の問題の配点は
p[i-1]点である。この問題の中から何問か解き、解いた問題の配点の合計が得点となる。このコンテストの得点は何通り考えられるか。

解法

dp[i][j] : i番目まで見て点数がjになる通り数
0≦i≦N、0≦j≦Σp[i-1]

dp[i][j]=dp[i-1][j]+dp[i-1][j-p[i-1]]
ただしj-p[i-1]<0の時は
dp[i][j]=dp[i-1][j]

i=0かつj=0のとき
dp[i][j]=1
i=0かつj≠0のとき
dp[i][j]=0

答えはi=Nのときのj≠0となる個数

ソースコード

signed main() {
	int N;
	cin >> N;
	vector<int>p(N);
	int Sp = 0;
	rep(i, N) {
		cin >> p[i];
		Sp += p[i];
	}
	vector<vector<int>>dp(N + 1, vector<int>(Sp + 1));
	rep(i, N + 1) {
		rep(j, Sp + 1) {
			if (i == 0 && j == 0) {
				dp[i][j] = 1;
			}
			else if (i == 0 && j != 0) {
				dp[i][j] = 0;
			}
			else if (j - p[i - 1] < 0) {
				dp[i][j] = dp[i - 1][j];
			}
			else {
				dp[i][j] = dp[i - 1][j] + dp[i - 1][j - p[i - 1]];
			}
		}
	}
	int ans = 0;
	rep(i, N + 1) {
		rep(j, Sp + 1) {
			if (i == N) {
				ans += dp[i][j] != 0;
			}
		}
	}
	cout << ans << endl;
}