放苹果
| Time Limit: 1000MS | Memory Limit: 10000K | |
| Total Submissions: 26595 | Accepted: 16906 |
Description
把M个同样的苹果放在N个同样的盘子里，允许有的盘子空着不放，问共有多少种不同的分法？（用K表示）5，1，1和1，5，1 是同一种分法。
Input
第一行是测试数据的数目t（0 <= t <= 20）。以下每行均包含二个整数M和N，以空格分开。1<=M，N<=10。
Output
对输入的每组数据M和N，用一行输出相应的K。
Sample Input
1 7 3
Sample Output
8
Source
简单的dp题，设dp[i][j]表示把i个苹果放入j个盘子里的方案数，盘子允许有空
如果i 或者j为1，那么方案就是1，如果i < j，必然有空盘子，但是空哪几个是无所谓的，所以 此时dp[i][j] = dp[i][i];
如果i == j，那么方案就是把i个苹果放入j-1个盘子的方案再加上一种平摊的方案
如果i > j，要么至少有一个盘子空，要么都有（先拿出j个平摊到j个盘子，在考虑剩下的i-j个苹果）
#include <map>
#include <set>
#include <list>
#include <stack>
#include <queue>
#include <vector>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
int dp[15][15];
int main()
{
int t, m, n;
memset ( dp, 0, sizeof(dp) );
for (int i = 1; i <= 11; ++i)
{
for (int j = 1; j <= 11; ++j)
{
if (i == 1 || j == 1)
{
dp[i][j] = 1;
}
if (i < j)
{
dp[i][j] = dp[i][i];
}
else if (i == j)
{
dp[i][j] = dp[i][j - 1] + 1;
}
else
{
dp[i][j] = dp[i][j - 1] + dp[i - j][j];
}
}
}
scanf("%d", &t);
while (t--)
{
scanf("%d%d", &m, &n);
printf("%d\n", dp[m][n]);
}
return 0;
}