poj1664（递推）

题目链接：http://poj.org/problem?id=1664

题目大意：如题

解题思路：有m个苹果和n个盘子，1.如果m<n，此时必然有n-m个盘子空着，因此f[m][n]=f[m][m];

2.如果m>=n，则分为两种情况，有至少一个盘子空着，或者是全部盘子都占满，此时只需要考虑每个盘子中都有一个苹果，剩下的苹果如何摆放，因此f[m][n]=f[m][n-1]+f[m-n][n];

AC代码;

#include <iostream>
using namespace std;
int main()
{int t;int n,m;int num[15][15];cin>>t;while(t--){cin>>m>>n;for(int i=0;i<=m;i++){num[i][0]=1;num[i][1]=1;}for(int i=0;i<=n;i++){num[0][i]=1;num[1][i]=1;}for(int i=2;i<=m;i++){for(int j=2;j<=n;j++){if(i<j)num[i][j]=num[i][i];if(i>=j)num[i][j]=num[i][j-1]+num[i-j][j];}}cout<<num[m][n]<<endl;}return 0;
}