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都能过............ (1416) 9974 2013-03-06 17:18:17
  • Re:本题若加强数据，以下4种dp都能过............ (0) 9974 2013-03-06 17:18:21