1664:Placing apples
http://bailian.openjudge.cn/practice/1664/
递归求解问题的经典分解
总Time Limit:1000msMemory Limit:65536kB
Description
We are going to place M same apples into N same plates.
There could be some empty plates.
How many methods do we have?
When we have 7 applesand 3 plates, the methods, (1, 5, 1) and (5, 1, 1) are the same.
Input
The first line is the number of test cases, t. 0<=t<=20
The next t lines are test cases containing two numbers, M and N. 1<=M, N<=10.
Output
Output the numbers of method in each test case in one line.
Sample Input
1
7 3

Sample Output
8
找到递归的子问题
首先 将问题分解为 m < n和m>n的情况,即有没有空盘子
当m < n 肯定至少有n-m个空盘子, f(m,n) = f(m,m);
当m > n, 可以将问题分解为有空盘子, 和没有空盘子
f(m,n) = f(m,n-1) + f(m-n,n);
f(m,n-1) 是指至少有一个空盘子的情况,
f(m-n, n) 是指先在所有的盘子里面都放一个苹果, 这样就没有空盘子了
所以代码如下

#include<iostream>
using namespace std;
int f(int m,int n){
    if(m == 0)
        return 1;//判断递归停止的条件,当没有苹果的时候, 这个时候不放苹果就是一种方法
    if(n == 0)
        return 0;//当没有盘子的时候, f(m,0) 肯定是零
    if(m < n)
        return f(m,m);

        return f(m,n-1) + f(m-n,n);

}int main(void){
  int N;
  cin>>N;
  while(N--)
  {
      int m,n;
      cin>>m>>n;
      cout<<f(m,n)<<endl;
  }

  return 0;}