再试递归与动态规划——Scratch编程解放球问题

（一）放球问题：

2023年全国青少年信息素养大赛Python复赛真题中倒数第二题是这样的：

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

输入描述：

输入一行两个正整数n, m，用空格间隔。

输出描述：

输出分配方案数。

例如：输入：5 10，输出：126

这个问题可以抽象成为一个排列组合问题：将m个球放入n个盒子中，这里（m≥n）,要求每个盒子至少有一个球。

和全错排问题一样，用穷举法解决很困难。

（二）算法分析

重点是寻找递推关系，也就是第n项和第n-1项之间的关系。

我们使用f(n, m)来表示m个球放到n个盒子里（每个盒子里至少一个小球）的方案数量，然后来分析第n个盒子和前n - 1和盒子之间的关系。

如果第n个盒子放1个小球，那么前面n - 1个盒子要存放 m - 1个小球，即f(n - 1, m -1)；如果第n个盒子放2个小球，那么前面n - 1个盒子要存放 m - 2个小球，即f(n - 1, m -2)；如果第n个盒子放3个小球，那么前面n -1个盒子要存放 m -3个小球，即f(n -1, m -3)；......如果第n个盒子放i个小球，那么前面n -1个盒子要存放 m - i个小球，即f(n -1, m -i)；

由于题目要求确保每个盒子至少1个小球，所以第n个盒子最少放1个小球，最多放m - n + 1个小球，即极端情况，其它n-1个盒子都只放一个，其余全放在第n个中。

再将所有的方案加起来就可以得到总的方案数量了，即：

盒n\球m

0

1

2

3

4

5

6

7

8

0

0

0

0

0

0

0

0

0

0

1

0

1

1

1

1

1

1

1

1

2

0

0

1

2

3

4

5

6

7

3

0

0

0

1

3

6

10

15

21

4

0

0

0

0

1

4

10

20

35

（三）递归编程实现

由于Scratch没有Python等编程语言那样的二维数组，要处理本例这样的两个变元的迭代函数式，就需要构建一个“长列表”替代二维数组。建立一个（n+1）*（m+1）的0元素列表，并把n=1时f(n,m)=1的初始结果放入。那么在递归结束时可以什么也不做。

(1)为确保n不超过m，用一个直到循环。

(2)建立一个长列表并将n=1时初始结果放在相应位置。

(3)建立递归程序计算f(n,m):

(4)输出结果：

（5）主程序和结果呈现：

也许是Scratch本身有短板，递归程序的弱点在这个例子中暴露无遗，计算耗时严重，就这点数据，许久都不出来。

用动态规划的思路实现，是否效率要高很多？？

（四）用动态规划思想推导递推公式

由于有了前面的递推公式，直接给出相关程序：

数据n和m比上面递归程序增加了不少，结果瞬间呈现，选择算法的重要性可见一斑。