下载掌阅APP，畅读海量书库
立即打开
在解答谜题时，很多处理会重复相同的计算，尤其是在解决递归问题时。将计算过一次的结果用在其他地方，可以提高程序的处理速度。
例如，我们来思考下面的问题。虽然单纯用递归处理也能解决，但如果用一些技巧，能大幅度缩短处理时间。
一群人去餐厅用餐，决定分桌坐，在分桌时要避免出现1张桌子只有1个人的情况。
此时，如果只考虑基于人数的分法，不考虑谁坐在哪一桌，那么以6人为例，共有以下4种分法。
● 2人 + 2人 + 2人
● 2人 + 4人
● 3人 + 3人
● 6人
如果1张桌子最多能坐10人，那么当有100人需要分桌坐时，有多少种分法？
如果给第1张桌子分配的人数已定，那么剩下的人只能被分配到剩余的桌子上。这时，桌子数要减去1，剩下的人数则是总人数减去分配到第1张桌子的人数（ 图0.1 ）。
图0.1 第1张桌子和剩余的桌子
由于桌子的数量没有上限，所以只要考虑人数的分配方式即可。因此，我们来考虑接下来是分配与之前那桌相等的人数，还是分配多于之前那桌的人数。
换句话说，只要知道剩余人数和之前那桌分配的人数，就可以递归地进行搜索。这样一来，我们就能知道程序的处理可以用“剩余人数”和“之前那桌分配的人数”这两个参数来实现。
我们先根据问题描述来实现程序，请看代码清单pre01.01和代码清单pre01.02。
答案 437420种
按照上面的方式虽然可以求出答案，但随着人数的增加，处理时间会呈指数级增长。这种处理方式的问题在于重复进行了相同人数的计算。我们可以试着改一下，把用过一次的值保存起来，在下次需要给同一个参数赋值时，直接返回保存的值就可以了（代码清单pre01.03和代码清单pre01.04）。
上述例子都在处理的最后保存了计算结果，这样一来，在后面的处理中，只要在处理的开头让程序返回保存的那个值就可以了。像这样使用存储好的值，可以迅速提升处理速度。在进行递归处理时，保存执行的结果，并在之后的处理中重复使用该结果的方法叫作内存化。
另外，上面这个解题方法是用递归函数来实现的，我们也可以用循环的方式来实现。如果用两个轴来表示就餐人数和每张桌子可分配人数的最大值，并像 图0.2 那样统计分法，那么就可以通过从比较小的数（ 图0.2 的左上角）开始，按顺序填入的方式来实现。
图0.2 通过循环方式推演的示意图
也就是说，先把就餐人数是0的那一列赋为1，然后从每张桌子可分配人数的最大值为2开始，反复计算所求单元格左边的数和上边的数之和，就能得到上面的表。
代码清单pre01.05和代码清单pre01.06是基于二重循环编写的示例代码，非常简洁。
这种方法叫作动态规划算法。听起来好像有点难，但如果你把它理解成就是将用过一次的计算结果存储起来，也就不难了。
本书会多次用到内存化这一实现方式。