Typical DP Contest A: コンテスト (動的計画法)

問題

A: コンテスト - Typical DP Contest | AtCoder

解法

dp[i][j]:=i問目まででj点に到達できるかどうか、を保存しておき、dp[N][i]をカウントする。

コード

import java.io.IOException;

public class Main {

	public static void main(String[] args) {
		int N = nextInt();

		int[] points = new int[N];
		int sum = 0;
		for (int i = 0; i < points.length; i++) {
			points[i] = nextInt();
			sum += points[i];
		}
		boolean[][] dp = new boolean[N + 1][sum + 1];// dp(i個入れて)(j点に到達可能か)
		dp[0][0] = true;
		for (int i = 0; i < N; i++) {
			for (int j = i; j >= 0; j--) {
				for (int k = sum; k >= 0; k--) {
					if (dp[j][k]) {
						dp[j + 1][k + points[i]] = true;
						dp[j + 1][k] = true;
					}
				}
			}
		}

		int count = 0;
		for (int i = 0; i <= sum; i++) {
			if (dp[N][i]) {
				count++;
			}
		}

		System.out.println(count);

	}

	static int nextInt() {
		int c;
		try {
			c = System.in.read();
			while (c != '-' && (c < '0' || c > '9'))
				c = System.in.read();
			if (c == '-')
				return -nextInt();
			int res = 0;
			while (c >= '0' && c <= '9') {
				res = res * 10 + c - '0';
				c = System.in.read();
			}
			return res;
		} catch (IOException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		}
		return -1;
	}

}