动态规划-放苹果

　　设f(m,n)为m个苹果，n个盘子的放法数目，则先对n作讨论，
　　　* 当n>m：必定有n-m个盘子永远空着，去掉它们对摆放苹果方法数目不产生影响。即if(n>m)f(m,n)=f(m,m)
　　　* 当n<=m：不同的放法可以分成两类：
　　　　(a)有至少一个盘子空着，即相当于f(m,n)=f(m,n-1);
　　　　(b)所有盘子都有苹果，相当于可以从每个盘子中拿掉一个苹果，不影响不同放法的数目，即f(m,n)=f(m-n,n).而总的放苹果的放法数目等于两者的和，即f(m,n)=f(m,n-1)+f(m-n,n)

作者：derrantcm
来源：CSDN
原文：https://blog.csdn.net/DERRANTCM/article/details/51864964
版权声明：本文为博主原创文章，转载请附上博文链接！

#include<stdio.h>
int main(){
    int m,n;
    while(scanf("%d%d",&m,&n)!=EOF){
        int dp[21][21];
        for(int i=0;i<=m;i++){
            dp[i][1]=1;
        }
        for(int i=0;i<=n;i++){
            dp[0][i]=1;
        }
        for(int i=1;i<=m;i++){
            for(int j=2;j<=n;j++){
                if(n>m)
                    dp[m][n]=dp[m][m];
                else
                    dp[m][n]=dp[m][n-1]+dp[m-n][n];
            }
        }
        printf("%d\n",dp[m][n]);
    }
}