> f3中dp[i][j]表示i个苹果放入j个箱子,且每个箱子至少放一个的种数。
> f4中dp[i][j]表示i个苹果放入j个箱子,但每个箱子可以为空的种数。
> #include <cstdio>
> #include <cstring>
> #include <iostream>
> using namespace std;
> int dp[11][11];
> int f1(int m, int n) { // 记忆化dp
> 	if(m < 0) return 0;
> 	if(dp[m][n]) return dp[m][n];
> 	if(n==1 || m == 0) return 1;
> 	dp[m][n] = f1(m-n, n) + f1(m, n-1);
> 	return dp[m][n];
> }
> void f2(int m, int n) { //背包dp
> 	int i, j, k;
> 	int dp[11][11] = {0};
> 	dp[0][0] = 1;
> 	for(i = 0; i <= m; i++) // 多组
> 		for(j = 1; j <= n; j++)
> 			for(k = i; k <= m; k++) // 多重
> 				dp[j][k] += dp[j-1][k-i];
> 	cout << dp[n][m] << endl;
> }
> void f3(int m, int n) { 
> 	int i, j;
> 	int dp[11][11] = {0};
> 	dp[0][0] = 1;
> 	for(i = 1; i <= m; i++)
> 		for(j = 1; j <= i; j++)
> 			dp[i][j] = dp[i-1][j-1] + dp[i-j][j];
> 	int ans = 0;
> 	for(i = 1; i <= n; i++) 
> 		ans += dp[m][i];
> 	cout << ans << endl;
> }
> void f4(int m, int n) { 
> 	int i, j;
> 	int dp[11][11] = {0};
> 	for(i = 0; i <= n; i++) dp[0][i] = 1;
> 	for(i = 0; i <= m; i++) dp[i][1] = 1;
> 	for(i = 1; i <= m; i++)
> 		for(j = 1; j <= n; j++) 
> 			dp[i][j] = dp[i][j-1] + ((i-j >= 0) ? dp[i-j][j] : 0);
> 		cout << dp[m][n] << endl;
> }
> int main() {
> 	int cas, m, n;
> 	cin >> cas;
> 	while(cas--) {
> 		cin >> m >> n;
> 		memset(dp, 0, sizeof(dp));
> 		cout << f1(m, n) << endl;
> 	}
> 	return 0;
> }

• Re:本题若加强数据，以下4种dp都能过............ (0) 9974 2013-03-06 17:18:21