很典型的动态规划题
很好的算法:
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;
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
int PlaceApple(int m, int n)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
if(m < 0)
return 0;
if(m == 0) //每个盘子一个
return 1;
if(n == 1) //只有一个盘子
return 1;
return PlaceApple(m - n, n) + PlaceApple(m, n - 1);
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
int main()
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
int num,m,n;
cin>>num;
while (num>0)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
cin>>m>>n;
cout<<PlaceApple(m,n)<<endl;
num--;
}
}