UVa 1213 - Sum of Different Primes

题目：计算整数n可以拆成k个不同的素数的拆分方法次数。

分析：动态规划（DP）、数论。二维01背包。

            首先，打表计算1120内的素数；

            然后，利用二维01背包算法算法求解；

            状态定义：f（k，i，j）为从前k个素数，取出j个不同的，组成数字i的方法数，prime[k]要取；

            转移方程：f（k，i，j）= sum（f（k-1，i-prime[k]，j-1），f（k-2，i-prime[k]，j-1），...）；

            为了避免重取，将k放在最外层，去掉对应的下标节省状态存储空间。

说明：好久没做Dynamic Programming了。

#include <stdio.h>
#include <stdlib.h>

int visit[1200] = {0};
int prime[1200]; 
int dp[1200][15] = {0};

int main()
{
	int prime_count = 0;
	for (int i = 2; i <= 1120; ++ i) {
		if (!visit[i]) {
			prime[prime_count ++] = i;
			for (int j = i+i; j <= 1120; j += i) {
				visit[j] = 1;
			}
		}
	}
	
	dp[0][0] = 1;
	for (int k = 0; k < prime_count; ++ k) {
		for (int i = 1120; i >= prime[k]; -- i) {
			for (int j = 1; j <= 14; ++ j) {
				dp[i][j] += dp[i-prime[k]][j-1];
			}
		}
	}
	
	int n, k;
	while (~scanf("%d%d",&n,&k) && n) {
		printf("%d\n",dp[n][k]);
	}
	
    return 0;
}