很典型的動態規劃題

很好的算法：
f(m, n) = f(m-n, n) + f(m, n-1)

f(m, n): 把m個蘋果放到n個盤子中的方法數
f(m, n-1): 把m個蘋果放到n-1個盤子中的方法數(其中至少有一個空盤子)
f(m-n, n): 把m個蘋果放到n個盤子中,而且每個盤子中都有蘋果(先拿n個出來,等m-n個放好了,然后每個盤子放一個)

一定要牢記！！！

#include <iostream>
#include <vector>
#include <string>
#include <math.h>
#include <iomanip>
#include <stdlib.h>
using namespace std;

int PlaceApple(int m, int  n)
{
    if(m < 0)
        return 0;
    if(m  == 0)   //每個盤子一個
        return 1;
    if(n == 1)   //只有一個盤子
        return 1;
    return PlaceApple(m - n, n) + PlaceApple(m, n - 1);
}

int main()
{
    int num,m,n;
    cin>>num;
    while (num>0)
    {
        cin>>m>>n;
        cout<<PlaceApple(m,n)<<endl;
        num--;
    }
}