网站建设 phpseo网站优化培训班
分配方案
描述
有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])递归和动态规划是解决很多算法问题的两种重要方法，尤其在处理需要重复子问题求解的问题时非常有效。尽管它们在某些方面相似，但在效率、内存使用以及实现方式上有着显著的区别。