FP难题不会解？STEP难题无从下手？

别着急，本文先带你解析思考一类递归问题的通用方法，需要抽出一点时间集中精力阅读，如时间有限可先收藏后看哦~

递归问题带来的启发：汉诺塔问题

我们首先来看一个小的谜题，汉诺塔问题，它由法国数学家卢卡斯（Edouard Lucas）于1883年发明。

有三个空柱子，最左侧的柱子上叠放着从小到大8个圆盘，圆盘的大小从上到下依次递增，如上图所示。

我们的目标是将所有的圆盘从最左侧的柱子移动到最右侧的柱子上，但有两个要求：一次只移动一个圆盘，小的圆盘必须落在大的圆盘上方。

我们的问题是：至少需要多少步才能将所有8个圆盘移到最右边的柱子上？

卢卡斯甚至将他发明的谜题包装成了一个印度的古老传说：梵天塔。印度教的主神梵天在创造世界的时候，在一块黄铜板上插着三根钻石针，并在其中一根针上从下到上地穿好了由大到小的64片金片。不论白天黑夜，总有僧侣在移动这些金片：一次只移动一片，小片必须在大片上面。僧侣们预言，当所有的金片都从梵天穿好的那根针上移到另外一根针上时，世界就将在一声霹雳中消灭，而梵塔、庙宇和众生也都将同归于尽。

回到问题中来，对于这类问题，我们不妨将其推广到n个圆盘的情况，这样做的一个好处是可以进一步减小问题的规模。

求解的第一步是建立直觉，而直觉往往是通过先看小的数字得到的。通过少量实验，可以很容易得知只有2~3个圆盘时所需要的步数。

*因无法编辑某些数学符号，以下讲解截图至郭老师文章内容。

汉诺塔问题是一类典型问题的代表。通过汉诺塔问题的研究，我们得到了解决求通项公式的一种通用思路：

1. 看小的数字的情况：解决规模小的问题可以帮助我们理解问题的本质

2. 发现并证明递推公式：建立大数字与小数字之间的联系

3. 发现并证明通项公式：用递推公式计算小的数字，猜想通项公式，并用数学归纳法证明

好了，这期的内容就是这些。如果觉得有用，记得分享给身边需要的人，我们下期见！