深入剖析斐波拉契数列
前言
动态规划作为一种非常经典的一类算法，不仅在解决实际问题当中有很多实际的应用，同时通常也是面试的一个重点。本篇文章一步步剖析动态规划的基本原理，通过斐波拉契数列问题（优化时间复杂度从$O(2^n)$到O(n)再到O(log(n))）一步一步带你从最基本的原理弄懂动态规划。我们首先分析斐波拉契数列问题，然后在分析问题的时候慢慢的深入动态规划。
斐波拉契数列
斐波拉契数列的定义如下：
$$ F_0 = 0 $$
$$ F_1 = 1 $$
$$ F_n = F_{n - 1} + F_{n- 2} $$
就是斐波那契数列由0和1开始，之后的斐波那契数就是由之前的两数相加而得出。比如说在斐波拉契数列当中第一个数为0，第二个数为1，因此第三个数为前面两个数之和，因此第三个数为1，同理第四个数是第二个数和第三个数之和，因此第四个数为2，下面就是斐波拉契数的变化：
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, ....
斐波拉契数列——递归法
现在我们的问题是要你求第n个斐波拉契数，这个问题还是比较简单的，很容易想到这就是一个可以递归解决的问题，在公式$F_n = F_{n - 1} + F_{n-2}$当中也容易看出应该使用递归。现在要确定的就是递归终止条件。
- 如果
n == 0则返回0，如果n == 1则返回1，这就是递归终止条件。