1073. 放苹果 _{(Standard IO)}

时间限制:

1000 ms  空间限制: 262144 KB  具体限制 

题目描述

把M个同样的苹果放在N个同样的盘子里，允许有的盘子空着不放，问共有多少种不同的放法（放法数用K表示）。如在7个苹果3个盘子的情况下, 5，1，1和1，5，1 是同一种放法。

输入

第一行是测试数据的数目t（0<=t<= 20）。以下每行均包含二个整数M和N(1<=M，N<=10)，以空格分开。

输出

对输入的每组数据M和N，用一行输出相应的K。

样例输入

17 3

样例输出

8

数据范围限制

0<=t<= 20, 1<=M，N<=10

 

分析：动态规划或递归都可以。

 

动态规划解法

dp[i][j]表示把i个苹果放在j个盘子上的所有方案,dp[N][M]就是答案。

当i<j时,盘子比苹果多，那么dp[i][j]=dp[i][i];

否则，dp[i][j]=dp[i][j-1]+dp[i-j][j],含有0的时候是dp[i][j-1](有空盘的时候)；

不含0的时候是dp[i-j][j],即所有盘子都有苹果,那么从每个盘子取走1个苹果后(总共取走j个),不影响放法数目,即dp[i-j][j],

因此有dp[0][j]=1(初始化);

#include
      
       int dp[20][20];int main(){    int N,M,T;    scanf("%d",&T);    while(T--)    {        scanf("%d%d",&N,&M);        for(int i=1;i<=N;i++)         dp[i][1]=dp[0][i]=1;//初始化         for(int i=1;i<=N;i++)        {            for(int j=1;j<=M;j++)            {                if(i
      

 

递归解法

f(i,j)的意义与dp[i][j]的意义相同。

#include
      
       int f(int n,int m){    if(n==0||m==1) return 1;    if(n