动态规划经典题目之三斐波那契数列

川长思鸟来 2022-05-14 00:21 207阅读 0赞

### 问题描述 ###

斐波那契数列 1 1 2 3 5 8 ... ... 求斐波那契数列的第n项和。

### 问题分析 ###

斐波那契数列的递推公式为 F(n) = 1,n=1,2; F(n) = F(n - 1) + F(n - 2), n >= 3;

采用递归的方式很容易写出代码，但是递归的代码虽然简单，却存在着大量的重复子问题，重复计算，时间复杂度高。例如，我们以求解F(5)为例，如下：

![70][]

红色的部分都是重复求解的，这仅仅是n=5时，当n=30时，子结构重复求解会大大浪费时间，时间，空间都会爆掉。

解法1：

我们直观想到的是，既然会重复求解，那只要记录下来求解过的就行了，下次计算前，先看看有没有计算过，如果已经计算过就不需要再次计算，这就是备忘录算法。但是，当n过大时，递归层数过多，空间也会爆掉。

解法2：

解法1是自顶向下进行递归求解。而DP是自底向上的求解问题，由初始状态一步步向上求的问题的解。对于斐波那契数列，初始状态为 F(1) = F(2) = 1, 那么我们可以依次求出

F(3),F(4),... ...F(n) ，同样的子问题，也是只需要求解一次，大大提高了计算效率。

### 递归求法代码 ###

#include <iostream>
    
    using namespace std;
    
    int fib(int N)
    {
        if(N == 1)
            return 1;
        ifa(N == 2)
            return 1;
        return fib(N-1) + fib(N-2);
    }
    
    int main()
    {
        int n;
        cin >> n;
        cout << fib(n) << endl;
    }

### 备忘录算法 ###

#include <iostream>
    
    using namespace std;
    
    int* fib_data;
    
    int fib(int N)
    {
    	if(N == 1)
    		return 1;
    	if(N == 2)
    		return 1;
    	if(fib_data[N] > 0)
    		return fib_data[N];
    	else {
    		fib_data[N-1] = fib(N-1);
    		fib_data[N-2] = fib(N-2);
    		return fib_data[N-1] + fib_data[N-2];
    	}
    }
    
    int main()
    {
    	int n;
    	cin >> n;
    	fib_data = new int[n + 1];
    	memset(fib_data,0,sizeof(int) * (n + 1));
    	cout << fib(n) << endl;
    }

### DP代码 ###

#include <iostream>
    
    using namespace std;
    
    long long dp_fib(int N)
    {
    	long long* fib_n = new long long[N + 1];
    	fib_n[1] = 1;
    	fib_n[2] = 1;
    	for (int i = 3; i <= N; i++) {
    		fib_n[i] = fib_n[i - 1] + fib_n[i - 2];
    	}
    	return fib_n[N - 1];
    }
    
    int main()
    {
    	int n;
    	cin >> n;
    	cout << dp_fib(n) << endl;
    }

[70]: /images/20220514/27b44a1e81824dfb8586172f6ba7abb7.png