题目描述
把 m 个不同的炮弹装入 n 个同样的炮口里,每个炮口至少装入1枚炮弹,问共有多少种不同的方案。
(提示:用f[i][j]表示将i枚炮弹装入j个炮口的方案数,第一种情况是第i枚炮弹单独装入1个炮口,对于前面的i-1个炮弹,它们只能装入j-1个炮口中,这种情况的方案数就是f[i-1][j-1]。
第二种情况是第i枚炮弹与其它的炮弹共同装入1个炮口中,在装入第i枚炮弹前已经有i-1枚炮弹装入了j个炮口中,这种情况的方案数就是f[i-1][j],
又因为装入了i-1个炮弹后,这j个炮口虽然炮口相同,但由于填入炮弹不同,因此有了多种方案——第i枚炮弹有j种选择,所以第二种情况的方案数就是f[i-1][j] * j。
因为f[i-1][j-1]和f[i-1][j]*j是两种不同的情况,所以最终的结果f[i][j] = f[i-1][j-1] + f[i-1][j]*j;)【数据范围】
1 <= m,n <= 10
输入
输入一行,两个整数m,n。
输出
一个整数,表示答案。
样例输入
4 2
样例输出
7