【例9】放苹果（POJ 1664）
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
（1）编程思路。
设f[m][n]表示把m个苹果放到n个盘子里的不同方法的种数。
1）当盘子数n为1的时候，只有一种放法，就是把所有苹果放到一个盘子里。
2）当苹果数m为1的时候，也只有一种放法，因为盘子之间并无顺序，所以不管这个苹果放在哪个盘子里，结果都算一个。
3）当m<n时，m个苹果最多只能放到m个盘子中去（一个盘子里放一个），盘子有多余的。此时，实际上就相当于把m个苹果放到m个盘子里一样，也就是f[m][m]。
4）当m>=n时，可分两种情况讨论。一种是至少有一个盘子里不放苹果，这就相当于f[m][n-1]；另一种是先取出n个苹果一个盘子里放一个，再将剩下的m-n个苹果放到n个盘子里去，即f[m-n][n]。
综上所述，可得到递推关系式如下：
f[m][n]=1 当m=1或n=1时
f[m][n] = f[m][m] 当m<n时
f[m][n] = f[m-n][n] + f[m][n-1] 当m>=n时;
另外，当m=0或n=0时，定义f[m][n]=1。即有盘子没苹果放，或者有苹果没有盘子装，都是一种可能存在的情况。这个可以特殊处理，就像0的阶乘定义为1一样。
（2）源程序。
#include <iostream>
using namespace std;
int main()
{
int f[11][11];
int t,n,m,i,j;
for (i=0;i<=10;i++)
{
f[i][0]=1;
f[i][1]=1;
f[0][i]=1;
f[1][i]=1;
}
for (i=2;i<=10;i++)
for(j=2;j<=10;j++)
{
if(i>=j)
f[i][j]=f[i][j-1]+f[i-j][j];
if(i<j)
f[i][j]=f[i][i];
}
cin>>t;
while(t--)
{
cin>>m>>n;
cout<<f[m][n]<<endl;
}
return 0;
}
【例10】Humble Numbers （POJ 2247）
Description
A number whose only prime factors are 2,3,5 or 7 is called a humble number. The sequence 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 12, 14, 15, 16, 18, 20, 21, 24, 25, 27, shows the first 20 humble numbers.
Write a program to find and print the nth element in this sequence.
Input
The inpu