逐层改进的斐波拉契数列--引入动态规划的思想

0x01.原始暴力递归方法

斐波拉契数列最原始的数学定义来源于递归，所以最开始是由递归解决斐波拉契问题的。代码如下：

int Fibonacci(int n)
{
	if (n == 1 || n == 2)
	{
		return 1;
	}
	return Fibonacci(n - 1) + Fibonacci(n - 2);
}

这个算法看起来很简单，但其实执行起来非常低效，为什么呢？

我们先来看一下这个时间复杂度，这个算法的时间复杂度主要由递归产生，每一次调用仅进行了加法和递归调用的操作，总共调用2的n次方次，那么这个时间复杂度是   ，指数级别，看到心头一颤。

我们仔细分析一下为什么效率低呢，按照常理来说，应该是只需要计算n次得。

我们模拟一下算法运行，加入传入50，那么先会递归调用49，48，49又会递归调用48，47，48又会递归调用46，47，，等等，你是不是已经发现了啥，没错，那就是48，47被反复得调用了，我们得目的最多只需要知道47，或者48，但是在这个递归调用得过程中，它被反复得调用了，这也就产生了很多不必要得重复，提升了时间复杂度，我们习惯称这种问题为：最小重叠子问题。

0x02.改进1--标记已求解

我们的想法是，如果把已经求出的中间问题标记起来，每当我们需要递归之前，先查询一下这个问题是否已经被解决，如果被解决，直接来拿用，如果没有，那么再进行递归，代码如下：

int Fibonacci(int n)
{
	if (n < 1)
		return 0;
	int *flag = (int*)calloc((n + 1),sizeof(int));//动态初始化一个数组
	return checker(flag, n);
}

int checker(int* flag, int n)
{
	if (n == 1 || n == 2)
		return 1;
	if (flag[n])//存在
		return flag[n];
	flag[n] = checker(flag,n-1) + checker(flag,n-2);//不存在则计算
	return flag[n];
}

这段代码充分实现了我们的想法，我们来计算一下时间复杂度。

因为这个算法不存在重复计算子问题的说法，所以，它的时间复杂度就是 O(n)。

0x03.改进2--一维基本动态规划

上述递归的做法是从n到1，2，既然有了这个思想，我们就可以从1，一直迭代到n，也就是基本动态规划的思想。

代码如下：

int Fibonacci(int n)
{
	int* dp = (int*)calloc(n, sizeof(int));
	if (n == 1||n==2)
		return 1;
	dp[0] = dp[1] = 1;
	for (int i = 2; i < n; i++)
	{
		dp[i] = dp[i - 1] + dp[i - 2];
	}
	return dp[n-1];
}

着就是最基础的一维动态规划，迭代关系可以从原始的递归过程中看出，由于是线性迭代，时间复杂度是 O(n)。

0x04.改进3--优化的动态规划

从时间复杂度上将，无可挑剔，不能再少了，但是从空间上来说，空间复杂度是 O(n)。

这个是否还可以优化呢？

答案是必然的，我们可以思考一下用这个长度为n的数组的目的，就是为了记录每一次迭代出来的值，但实际上我们使用了所有的值嘛，并没有，我们在一次循环中，只使用了两个dp数组中的值，这两个值其实是可以用变量来代替的，只需要不断的更新就行了，这样，空间复杂度就可以降为 O(1)。它也香~~~

代码如下：

int Fibonacci(int n)
{
	if (n == 1 || n == 2)
		return 1;
	int pre=1, cur=1;//前两次迭代的结果和前一次迭代的结果
	int sum;//本次的值
	for (int i = 2; i < n; i++)
	{
		sum = pre + cur;
		pre = cur;
		cur = sum;
	}
	return cur;
}

这个动态规划的算法已经优化到极致，不可以继续优化了，这样使用的动态规划，才是真的用好了动态规划！！！

0x05.从中得到的动态规划启示

• 动态规划其实就是解决最小重叠子问题的一个方法。
• 动态规划的关键是找准迭代表达式（也叫状态转移方程）和初始条件（也叫基准）。
• 迭代表达式可以从递归中获取思路。
• 初始条件往往是递归从后向前的结束条件。
• 递归优化的过程，就是动态规划的逆向过程。
• 动态规划的空间复杂度往往是可以考虑优化的。

如果本文对你有帮助，分享给更多朋友吧。

ATFWUS  --Writing By 2020--03--14