m个求放入到n个瓶子的组合数

题目描述

要把m升的水倒入n个相同的容器中（假设容器足够大），允许有的容量是空的，问共有多少种不同的倒法？（用k表示）5，1，1和1，5，1和1，1，5是同一种倒法。

输入描述:

第一行是测试数据的数目x(0≤x≤20)。以下每行均包含二个整数m和n，以空格分开。1≤m，n≤10。

输出描述:

对输入的每行数据m和n，用一行输出相应的k。

示例1

输入

复制

1 7 3

输出

复制

8

#include<iostream>
using namespace std;
 
int main(){
    int x,m,n,up,ans;
    int dp[11][11];
    for(int j=0;j<11;j++){
        dp[0][j] = 0;
        for (int i=j+1;i<11;i++){
            dp[i][j] = 0;
        }
    }
     
     
    for(int i=0;i<11;i++)
        dp[i][0] = 0;
     
    dp[0][0] = 1;
    for(int i=1;i<11;i++){
        for(int j=i;j<11;j++){
            dp[i][j] = dp[i-1][j-1] + dp[i][j-i];
        }
    }
     
    cin>>x;
    for(int i=0;i<x;i++){
        cin>>m>>n;
        up = n<m?n:m;
        ans = 0;
        for(int k=1;k<=up;k++){
            ans+=dp[k][m];
        }
        cout<<ans<<endl;
    }
    return 0;
}