AlgoPressAppearance
0509-斐波那契数
https://leetcode.cn/problems/fibonacci-number/
斐波那契数，通常用 F(n) 表示，形成的序列称为 斐波那契数列 。该数列由 0 和 1 开始，后面的每一项数字都是前面两项数字的和。也就是：
F(0) = 0，F(1) = 1 F(n) = F(n - 1) + F(n - 2)，其中 n > 1 给你 n ，请计算 F(n) 。
思路分析
递归思路 Fib(n) = Fib(n-1) + Fib(n-2)， 退出条件为 n = 0, return 0, n = 1, return 1.
递归解法会存在重复计算，比如 F(4) 会计算 F(3) 和 F(2)， 而计算 F(3) 的时候 优惠计算 F(2) 和 F(1)，这里 F(2)就会重复计算
动态规划，先计算前面的结果只，后面的值在前面的基础上在计算，计算好的值用数组存储下来，这样就不会重复计算。
F(0) = 0 , F(1) = 1, F(2) = F(0) + F(1), F(3) = F(1) + F(2)
注意动态规划最终的一点，就是缓存中间数据和设置状态转移方程，这里的状态转移方程就是 F(n) = F(n-1) + F(n-2)
实现代码
暴力递归解法(存在重复计算)
csharp
public class Solution {
public int Fib(int n) {
if(n == 0 || n == 1){
return n;
}
return Fib(n-1) + Fib(n-2);
}
}
暴力法：空间换时间
csharp
public class Solution{
//定义字典储存中间值
private Dictionary<int,int> dict = new Dictionary<int,int>();
public int Fib(int n){
if(n == 0 || n == 1){
return n;
}
int result = 0;
if(dict.ContainsKey(n)){
result = dict[n];
}
else{
result = Fib(n-1) + Fib(n-2);
if(!dict.ContainsKey(n)){
dict.Add(n,result);
}
}
return result;
}
}
动态规划解法
csharp
public class Solution{
public int Fib(int n){
if(n <= 1 ){
return n;
}
int[] dp = new int[n+1];
dp[0] = 0;
dp[1] = 1;
for(int i=2; i<=n; i++){
dp[i] = dp[i-1] + dp[i-2];
}
return dp[n];
}
}
动态规划解法2 滚动数组
注意这里的状态转移方程 F(n) = F(n-1) + F(n-2)，所以最终的要计算的值，之和该数的前两位相关，所以我们只需要保存前两位的值和当前的和即可，不需要存储整个数组
csharp
public class Solution{
public int Fib(int n){
if(n <= 1){return n;}
int num1 = 0;
int num2 = 1;
int sum = num1 + num2;
for(int i=2; i<=n; i++){
sum = num1 + num2;
num1 = num2;
num2 = sum;
}
return sum;
}
}