POJ 1664 放苹果 递推
思路：将n分成k个数的和，表示成fun(n,k)，可以分成两种情况，一种是k个数中至少含有一个0，这样的情况有fun(n,k-1)种，再加一个0即可。另外一种情况是不含0。既然不含有0，则每个数至少为1，即转化为将n-k个数分成k个数，即是fun(n-k,k)。所以fun(n,k) = fun(n,k-1) + fun(n-k,k)。处理好零界条件即可。
代码：
[cpp] www.zzzyk.com
#include <iostream>
#include <cstdio>
#include <string.h>
using namespace std;
#define CLR(arr,val) memset(arr,val,sizeof(arr))
int fun(int n,int k){
if(k == 1 || n== 0)return 1;
if(n < k)return fun(n,n);
return fun(n,k-1) + fun(n-k,k);
}
int main(){
//freopen("1.txt","r",stdin);
int numcase;
scanf("%d",&numcase);
int n,k;
while(numcase--){
scanf("%d%d",&n,&k);
int ans = fun(n,k);
printf("%d\n",ans);
}
return 0;
}
作者：wmn_wmn
补充：软件开发 , C++ ,
