从一个问题开始
假如有 7 个台阶，每次你可以跨 1 个台阶或者 2 个台阶，那么走这 n 个台阶有多少种走法？你可以 2、2、2、1 这样子上去，也可以 1、2、1、1、2 这样子上去，也可以 1、2、1、1、2 这样子上去，总之走法有很多，那总共究竟有多少种走法呢？
最近在学习极客时间里的王争的《数据结构与算法之美》，以上是其中举的一道例题。
穷举
我一开始是一头雾水的，不知从何下手。王争老师给出了思路，可以根据第一步的走法把所有的走法分为两类，第一类是第一步走了1 个台阶，另一类是第一步走了 2 个台阶。然后对于后面的第一步走法，都可以这样分类。
我先暴力穷举，用这种思路画了一下，用圆形代表一次走一个台阶，用矩形代表一次走两个台阶：
如果一共只有 1 个台阶
只有一种走法，对应的图中要从根节点到叶子节点只有一条路径。
如果一共是 2 个台阶
一共有两种走法，对应的图中要从根节点到所有的叶子节点，有两条路径。
如果一共是 3 个台阶
如果一共是 4 个台阶
画到这里，我已经看出了规律，对于 4 个台阶的走法树形图，是由 3 个台阶的走法树和 2 个台阶的走法树分别做为其左子树和右子树拼成的，左子树一共有 3 条路径，而右子树一共有 2 条路径，形成的新的树，就是左右子树路径之和，即 5 条路径，也就是一共有 5 种走法。
如果一共是 5 个台阶
一共 8 种走法，对应 8 条路径，也即 8 个叶子节点。
如果一共是 6 个台阶
一共 13 种走法，对应 13 个叶子节点。
如果一共是 7 个台阶
不用想就是 21 种走法，也即 21 个叶子节点。
递归
要写代码来计算的话，可以先假设问题已经得到了解决，由于并不知道真正的答案，可以用一个代号来表示。由于不同的台阶数有不同的结果，所以这个代号还得有一个编号。对于七级台阶，不妨假设有f(7)种走法。在上面的穷举中，已经知道了，对于n级台阶，都可以在第一步时，分成是一步走一个台阶还是一步走两个台阶这两种情况。对于7级台阶，第一步如果是走一个台阶，那么还剩下6级台阶，即f(6)种走法。如果第一步走了两个台阶，那么还剩下5级台阶，即f(5)种走法。
总之，f(7)=f(6)+f(5)。
终止条件
以上，显然，f(n)=f(n-1)+f(n-2)。在穷举中我们知道了，f(1)=1，f(2)=2。
最张递推式
f(n) = f(n-1) + f(n-2), n > 2
f(2)=2
f(1)=1
你可能早就看得不耐烦了，这不就是斐波那契数列吗！我反应慢，我是到了这一步才突然意识到，咦，这个问题的解决方法怎么就和斐波那契数列产生了关系呢？突然感觉到一股神奇的力量！不仅如此，仔细回看穷举图，还发现有分形呢！
最终代码
既然是斐波那契数列，那这个代码我可太会写了！
javascript function f(n) { if (n === 1 || n === 2) { return n; }
return f(n-1) + f(n-2); }
再一次怀疑人生，因为我自认为对斐波那契数列是非常熟悉的，但却一开始不会这道题！这种感觉就像，遇见一道门，被锁上了。而钥匙明明就在手中，却仍然不知道怎么打开门。
优化
我对斐波那契数列真是太熟悉了，并且非常喜欢用它来做为面试题。在聊正题前，总会先对面试者说，用你最熟悉的语言写一个计算斐波那契数列第n项的函数吧。我竟然经常碰到面试者没听过这个数列，于是就耐心地解释，这个数列有这样的特征，第1项是1、第2项是2、从第3项开始，其值都是前两项之和，比如第3项是3，第4项是5，第5项是8，如此类推。
如果有人恰好写出来了，并且用的是我最喜欢的 JavaScript，我就会再刁难一下：这个是对的，但是效率不高，存在重复计算，你能再优化一下吗？
我心中的答案当然是用缓存。一个示例如下：
javascript const cache = {};
function f(n) { if(cache[n]) { console.log(缓存命中： , n); return cache[n]; }
console.log(计算 n = , n);
if (n === 1 || n === 2) { console.log(计算 n = , n, . f(n) = , n);
cache[n] = n;
return n;
}
const result = f(n - 1) + f(n - 2);
console.log(计算 n = , n, . f(n) = , result);
cache[n] = result; return result; }
console.log(f(7));
我最喜欢的缓存写法是利用记忆函数 memoize，自己实现这个 memoize 或者是使用一些库中提供的，都可以。
我曾经自己实现过一个，详见《(闭包的妙用 —— memoize - Jeff Tian的文章 - 知乎)[https://zhuanlan.zhihu.com/p/353365352] 》。
但是如果要让这种 memoize 函数发挥效果，就需要改写一下递归函数的写法。也就是说，如果不对递归函数本身的写法进行改变，直接套用 memoize 就会失效。不信你可以试试，但应该怎么改写呢？大致思路是将函数自己做为一个参数传进去，在递归调用时，不要直接调用自己，而是调用这个参数函数，不过还没有验证过，欢迎热心网友给出一些实现。
超纲实现
通过使用缓存，可以将时间复杂度从O(2^n)降低到 O(n)。但是空间复杂度增加了，有的面试者通过迭代循环的方式，也能实现O(n)时间复杂度，同时不增加空间复杂度。但是有一次一个面试者，直接写出了如下实现：
javascript function f(n) { const phi = (1 + Math.sqrt(5)) / 2;
return Math.round( ( Math.pow(phi, n+1) - Math.pow(-phi, -(n+1)) ) / Math.sqrt(5) ); }
console.log(f(7));
我看了之后惊呆了，这是啥？心想：你不会就不会，可以直说啊，瞎蒙什么呀！于是笑笑对他说：我觉得我们没有必要聊下去了。面试者看到我懵逼的神情，也摇了摇头笑着叹了口气，说同意，没必要聊下去了。
这件事过去了很多年，我最近开始学习《离散数学》了，因为不想再做一个野生的程序员，所以开始补课了。学到一种叫做 Closed Formula 封闭公式的东西，突然听到老师提到了斐波那契数列的封闭公式，我突然觉得似曾相识！这不就是多年前那个面试者写的实现吗？我赶紧重新写了一下运行试试看：
答案完全正确，并且实现了 O(1) 的时间和空间复杂度！
我脸红了……
故事点估算方法
我脸红了，但是很快我释然了：我只是一个一线搬砖的程序员而已，哪里会这些高深的东西！而且再说了，什么斐波那契数列，平时搬砖根本用不到呀！
没想到，很快就用到了，而且每两周都要和它打交道一到两次，那就是故事点估算环节。
以前，我抱怨过，认为敏捷开发方法被实际落地中被歪曲了，还发了篇报怨文章《程序员，困在敏捷里 - Jeff Tian的文章 - 知乎 》。但是后来进入了一个还算正确使用敏捷方法的团队，每两周会固定一个时间开待办事项梳理会议，还会看情况不定时增加一个额外的梳理会议。在会议上，有一个环节，就是对故事进行复杂度估计。这个估算在不同的团队中有不同的做法，这里分享一下我们的做法。
我们采用的正是斐波那契数列来进行估算的，梳理会议上的流程大致是这样，产品经理打开一个故事详情，大家先看，看完后不许提问，大家先给出自己的估算结果，这个结果是斐波那契数列中的一个数字。
如果一致，则开始看下一个用户故事详情。如果不一致， 就开始讨论和提问，直到大家达成一致。
尽管有很多工具，特别是我们使用了 JIRA ，它自带了一个估算工具，但是我们采用了https://hatjitsu.toolforge.org/，它足够简单，使用方便。我们估算的原则大致如下：
故事的复杂度既包含了固有的复杂度，也包含了一些不确定性。如果不确定性很高，那么复杂度也会很高。因为不确定性高的话，就会涉及到额外的调研、探索和其他的消除不确定性的工作。
0：没有复杂性
这个用户故事微不足道，不需要工作量。要么是已经实现了，或者是太简单以至于用不着讨论。
1：非常低的复杂性
这个用户故事非常简单直接，可以很快完成，只需要最小的工作量，并且不存在完成它的风险。
2：低复杂度
这个故事很简单，但是比1所需要的工作量更多。可能会涉及一些小的配置工作，或者需要处理一些比较容易的小改动。
3：普通复杂度
这个用户故事有一定的复杂性，但仍然是在可控的范围内。要完成它不会碰到太多麻烦，尽管会涉及到多个步骤，或者需要一些基本的问题解决能力。
5：可观的复杂性
这个故事的复杂必已经开始引入注意了，它需要规划，并且需要多个步骤来完成它。并且可能存在一些不确定性以及和其他的任务存在相互依赖。
8：高复杂度
这个故事比较复杂，需要非常大的工作量。甚至可能需要多个团队成员相互协作来完成。有很大的概率会碰到问题，需要反复复查和修改。
13：非常高的复杂性
这个故事非常复杂 ，需要特别多的时间资源来完成。涉及到高风险、多依赖以及很大程度上的不确定性。如果故事复杂度达到这个点数，就需要考虑分解成更小的更可控的多个故事了。
21：极端复杂
这个故事极端复杂，几乎快要过于复杂了。它涉及多个团队、需要大量的计划，实现时大概率会碰到严重的问题。对于这种复杂度，几乎总是需要分解成更多的更小的更可控的故事。
34：超纲复杂度（爆表复杂度）
这个故事如此复杂以至于不可能给出一个合理的复杂度估计。它需要被分解成一些更小的任务，并且在分解之后再次评估。
以几个小问题结束
不知道你们平时有用到斐波那契数列吗？是在什么场景呢？你们又是怎么实践敏捷开发的？以及如何对用户故事进行估算的呢？
附
穷举部分用的文本绘图源码：
plain graph TD; A{0} -- 第一步 --> A1((1)) A -- 第一步 --> A2[2]
A1 -- 第二步 --> A11((1))
A1 -- 第二步 --> A12[2]
A2 -- 第二步 --> A21((1))
A2 -- 第二步 --> A22[2]
A11 -- 第三步 --> A111((1))
A11 -- 第三步 --> A112[2]
A12 -- 第三步 --> A121((1))
A12 -- 第三步 --> A122[2]
A21 -- 第三步 --> A211((1))
A21 -- 第三步 --> A212[2]
A212 -- 第四步 --> A2121((1))
A22 -- 第三步 --> A221((1))
A221 -- 第四步 --> A2211((1))
A111 -- 第四步 --> A1111((1))
A111 -- 第四步 --> A1112[2]
A112 -- 第四步 --> A1121((1))
A121 -- 第四步 --> A1211((1))
A211 -- 第四步 --> A2111((1))
A2111 -- 第五步 --> A21111((1))
A1111 -- 第五步 --> A11111((1))
A22 -- 第三步 --> A222[2]
A211 -- 第四步 --> A2112[2]
A122 -- 第四步 --> A1221((1))
A121 -- 第四步 --> A1212[2]
A1211 -- 第五步 --> A12111((1))
A1121 -- 第五步 --> A11211((1))
A1112 -- 第五步 --> A11121((1))
A11111 -- 第六步 --> A111111((1))
A1111 -- 第五步 --> A11112[2]
A112 -- 第四步 --> A1122[2]
A111111 -- 第七步 --> A1111111((1))
A11112 -- 第六步 --> A111121((1))
A11121 -- 第六步 --> A111211((1))
A1122 -- 第五步 --> A11221((1))
A11211 -- 第六步 --> A112111((1))
A1121 -- 第五步 --> A11212[2]
A1112 -- 第五步 --> A11122[2]
A12111 -- 第六步 --> A121111((1))
A1211 -- 第五步 --> A12112[2]
A1212 -- 第五步 --> A12121((1))
A1221 -- 第五步 --> A12211((1))
A122 -- 第四步 --> A1222[2]
A21111 -- 第六步 --> A211111((1))
A2111 -- 第五步 --> A21112[2]
A2112 -- 第五步 --> A21121((1))
A2121 -- 第五步 --> A21211((1))
A212 -- 第四步 --> A2122[2]
A2211 -- 第五步 --> A22111((1))
A221 -- 第四步 --> A2212[2]
A222 -- 第四步 --> A2221((1))
A11111 -- 第六步 --> A111112[2]