POJ - 1664 放苹果

把M个同样的苹果放在N个同样的盘子里，允许有的盘子空着不放，问共有多少种不同的分法？（用K表示）5，1，1和1，5，1 是同一种分法。

Input

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

Output

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

Sample Input

1 7 3

Sample Output

8

分析:   dp[i][j] 表示 i 个苹果 放在 j 个盘子里的摆放方案数 , 边界 dp[0][j] 没有苹果,光盘子算一种, 

            苹果的数量 n  和  盘子的数量  可能会出现 n>m  , n <m 和 n =m  ,三种情况 , 

             1  当n < m  苹果少的时候,多余的盘子不会影响方案数,(想想为什么 ,题目中说了 5 1 1 , 1 1 5 是重复的)

                   所以, 盘子再多又用不上,一直就是空着,对方案数有影响的是 n 个盘子的苹果摆放情况 .  

            你看这个,  , 1 0 1 0 , 1 1 0 0 ,  1 0 0 1 .. .. 这都是一种 , 2 0 0  0 , 0 0 0 2 ... 也是一种 

             2  当 n>=m 时 ,可以分成两种情况, 至少有一个盘子是空的 和 所有的盘子都有苹果 , 

                     ①  第一种情况 , dp[i][j] = dp[i][j-1] 

                     ②  第二种情况  ,每个盘子都拿掉一个苹果,还剩 i - j 个 苹果 放在 j  个盘子的方案数 , ,dp[i][j] = dp[i-j] [j] ;

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <set>
#pragma GCC optimize(2)
#include <cmath>
#define pi 3.141592654
using namespace std ;
const int MAX = 1005 ;
typedef long long LL ;
int dp[20][20] ;
int main(){
  int t ;
  cin >>t ;
  while(t--){
    int n ,m ;
    cin >> n >> m ;
    for(int i =0 ; i<=m ; i++ ) {
      dp[0][i] = 1 ;
    }
    for(int i = 1 ; i<=n; i++ ) {
      for(int j = 1 ; j<=m ; j++){
        if(i <j){ // 如果苹果的个数比盘子的个数少 ,那么一定会有i-j个
        // 盘子是空的 ,去掉他们对摆放苹果方法没影响
          dp[i][j]= dp[i][i] ;
        }
        else{
//    当n<=m：不同的放法可以分成两类：
//        1、有至少一个盘子空着，即相当于f(m,n) = f(m,n-1);
//         2、所有盘子都有苹果，相当于可以从每个盘子中拿掉一个苹果,一共拿了n个,还剩m-n个，不影响不同放法的数目，即f(m,n) = f(m-n,n).
//        而总的放苹果的放法数目等于两者的和，即 f(m,n) =f(m,n-1)+f(m-n,n)
          dp[i][j] = dp[i-j][j] +dp[i][j-1] ;
        }
      }
    }
    cout<<dp[n][m]<<endl;
  }
  
  
  
}