AOJ0097 Sum of Integers II

問題リンク Sum of Integers II

• 解法

DPです。
dp[N][X][S]: X以下の数字から異なるN個を選んで、和がSになる組み合わせ数
という表を埋めれば解けます。

• 解法2

DPですが、
dp[N]: 2個の数字を使って和がNになる組み合わせ
という表を用意して
dp[i] * dp[N-i]
の総和を取る方が断然簡単ですね

• ソース

import java.util.Scanner;

//Sum of Integers II
public class AOJ0097 {

	long[][][] dp;
	
	long get(int rest, int x, int s){
		if(rest==0 && s==0)return 1;
		if(rest<0 || x<0 || s<0)return 0;
		if(dp[rest][x][s]!=-1)return dp[rest][x][s];
		long res = 0;
		for(int nx=x;nx>=0;nx--)res+=get(rest-1, nx-1, s-nx);
		return dp[rest][x][s] = res;
	}
	
	void run(){
		Scanner sc = new Scanner(System.in);
		dp = new long[10][101][1001];
		for(int i=0;i<10;i++)for(int j=0;j<=100;j++)for(int k=0;k<=1000;k++)dp[i][j][k]=-1;
		for(;;){
			int n = sc.nextInt(), S = sc.nextInt();
			if((n|S)==0)break;
			System.out.println(get(n, 100, S));
		}
	}
	
	public static void main(String[] args) {
		new AOJ0097().run();
	}
}

import java.util.Scanner;

//Sum of Integers II
public class AOJ0097 {

	void run(){
		Scanner sc = new Scanner(System.in);
		long[] dp = new long[2001];
		for(int i=0;i<=1000;i++)for(int j=0;j<=1000;j++)dp[i+j]++;
		while(sc.hasNext()){
			int N = sc.nextInt();
			long res = 0;
			for(int s=0;s<=2000;s++)if(0 <= N-s && N-s <= 2000)res+=dp[s]*dp[N-s];
			System.out.println(res);
		}
	}
	
	public static void main(String[] args) {
		new AOJ0097().run();
	}
}