斐波那契数列 | 动态规划 | 练习

今日打卡：动态规划

从最简单的题目开始学习算法的思想是正确掌握算法，理解算法的重要途径。

动态规划的思想

• 穷举，但是要做的事情只做一遍
• 结果储存下来，如果有需要直接调用这个结果

斐波那契数列的定义：f(1)=1, f(2)=1，f(n)= f(n-1) + f(n-2)

也许你可以直接写出一个式子

// 使用递推的方式
int a=1, b=1;
for(int i=3; i<=n; i++){
	int c = a + b;
	b = a;
	a = c;
}

这仅是最简单的一个递推（动态规划的最优版本）

• 来看最简单的斐波那契数列的递归版本

int fib(int n){
	if(n==1 || n==2) return 1;
	int n = fib(n-1) + fib(n-2); // 根据给出的定义：每一个数n都需要知道n-1和n-2
	return n;
}

那么此时，已经知道了斐波那契数列的暴力递归

• 既然每一个数n斗都与n-1和n-2有关，那么给定的任意一个数n，让函数一直调用自己即可

但是经过分析和运行发现：暴力递归的用时实在是太长了

• 原因：用时太长
• 分析：重复计算过多

怎么分析得到的是很多重复计算呢？只需要举几个例子就可以知道，重复计算太多

既然是重复，那么也就是说，肯定是有相同的计算过程

每一次的计算结果储存起来不就可以了

分析以下计算的过程

• 需要知道n，那么前提需要知道n-1，n-2
• 需要知道n-1，那么前提需要知道n-2，n-3
• …
• f(1)=1, f(2)=1

• 从上面的计算的过程中可以知道，仅仅是写出来的就重复计算一次，那么用一个备忘录储存起来整个数据，每次计算之前查找一下备忘录，如果有，直接返回，如果没有再计算。

• 此时也就是说用一个数组，这个数组的长度是n，因为从1到n最多也就是n个数字

int[] memo  = new int[n]; // 初始化就为0，因为斐波那契数列的元素都不为0，如果检查到是0，那么说明还未计算过

int fib(int[] memo, int n){
	if(n==1 || n==2) return 1;
	if(memo[n] != 0) return memo[n]; // 查找备忘录，第n个的数字中，是否已经计算过
	memo[n] = fib(n-1) + fib(n-2); // 将计算的结果储存起来
	
	return memo[n];
}

此时就是自顶向下的分析方法了

能够写出这个动态规划的版本就可以了，不需要将所有的时间都花在学习递推上，如果真的感兴趣或者很容里就理解了从递归到自顶向下到递推，那么就去学

如果直接去看递推版本的动态规划，肯定很难，但是只要知道了是从自顶向下到递推的那么也就能看懂递推的过程，可能写不出来，但是最起码还是能看得懂到底在做什么

分析好状态转移，就是当前对象依赖于什么，每次的过程都是相似的依赖吗，将计算的结果储存起来了吗