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.2cto.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