面试题 n个小孩拿n个苹果 转载

面试题——n个小孩拿n个苹果

有n个苹果，n个小孩排队一个个地去拿苹果，每一个小孩在剩下的苹果中至少拿1个，至多全拿光。编程输出所有可能的拿法。（百度2008年面试题）

我一看到这个问题就想到了0-1背包问题：每个小孩可以拿1到n个，看成n种规格的物品放入大小为n的背包，用递归方法解出。但事实上，这道题没有这么复杂，让我们以n=4为例，按一定顺序列出所有的拿法：

4 0 0 0
3 1 0 0
2 2 0 0
2 1 1 0
1 3 0 0
1 2 1 0
1 1 2 0
1 1 1 1

可以得出这样一个规律：第n+1行的数列可以在第n行的基础上用如下的算法计算出：从右至左找到第一个大于1的数字，将它减1，然后将这个数字右边的数字赋为苹果总数减去左边所有数字后剩下的值，其余更右边的数全赋为0。