很典型的動(dòng)態(tài)規(guī)劃題

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

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

一定要牢記！！！

#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)   //每個(gè)盤(pán)子一個(gè)
        return 1;
    if(n == 1)   //只有一個(gè)盤(pán)子
        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--;
    }
}