有n个人，他们需要分配m元钱(m＞n)，每个人至少分到1元钱，且每个人分到的钱数必须是整数。请问有多少种分配方案?

分配方案

描述
有n个人，他们需要分配m元钱(m>n)，每个人至少分到1元钱，且每个人分到的钱数必须是整数。请问有多少种分配方案?
输入
一行，两个整数，分别是人数n与钱数m，用一个空格隔开。

输出
一行，一个整数，是分配方案数。

样例输入

5 10

样例输出

126

问题分析

1. 初始状态:

如果没有人(即i=0)，那么没有方案，方案数为0。

如果没有钱(即j=0)，那么唯一的方案就是所有人都分到 0 元钱，但这种情况不符合每个人至少1 元钱的条件，方案数为0。

如下表所示：

2. 状态转移方程 ：

如i=3，j=5，代表我们将5元钱分给3个人，方案数用f(i,j)表示，所有方案如下：

最后一人分1元，其余两人分剩余的4元，方案数为f(i-1, j-1)；

最后一人分2元，其余两人分剩余的3元，方案数为f(i-1, j-2)；

最后一人分3元，其余两人分剩余的2元，方案数为f(i-1, j-3)；

最后一人分4元，其余两人分剩余的1元。不符合要求，方案数为0；

最后一人分5元，其余两人分剩余的0元。不符合要求，方案数为0。

综上所述，方案数计算如下：

f(i,j) = f(i-1,j-1) + f(i-1, j - 2) + … + f(i -1, i-1)

因为 f(i-1, j - 2) + … + f(i -1, i-1) = f(i, j-1)

所以状态转移方程为：f(i,j) = f(i-1,j-1) + f(i, j-1)

3. 边界条件:

我们定义一个二维列表dp ，其中dp[i][j]表示将j元钱分配给i个人的方案数。

dp[1][1]=1表示1个人，1元钱，只有一种方案。

m<n时，钱数少于人数，方案数为0。

4. 参考代码

参考代码【递归】

def f(n, m):if m < n:return 0if n == 1:return 1count = 0for i in range(1, m - n + 2):# 递归计算 f(i-1,j-1) **+ f(i-1, j - 2) + ... + f(i -1, i-1)#  i的值最大为m-n+1count += f(n - 1, m - i)# 从f(n-1, m-1) 到 f(n-1, m-(m-n+1))即f(n-1,n-1)累加求和return countn, m =map(int,input().split())
print(f(n, m))

参考代码【动态规划】

n, m = map(int,input().split())
dp =[[0]*(m+1) for i in range(n+1)]
for j in range(1, m+1):dp[1][j]=1  # 大于等于1元时，只有1人分配方案有1种
for i in range(2, n+1):for j in range(i, m+1):# 从i开始，j小于i不需要计算dp[i][j]= dp[i-1][j-1] + dp[i][j-1]
print(dp[n][m])

递归和动态规划是解决很多算法问题的两种重要方法，尤其在处理需要重复子问题求解的问题时非常有效。尽管它们在某些方面相似，但在效率、内存使用以及实现方式上有着显著的区别。

↓ 更多少儿编程知识点 击 gzh 名 片 关 注查看 ↓