动态规划——斐波那契数列三种解法

叁歲伎倆 2022-10-07 00:50 193阅读 0赞

# 一、基本概念 #

动规是非递归的一种代码可以保存下来一些过程的解  
**1. 把原来的为标题分解成几个相似的子问题  
2. 所有的子问题都只需要解决一次  
3. 储存子问题的解**

动规本质：**是对问题状态的定义和状态方程的定义**（状态以及状态之间的递归关系）

动态规划问题一般从以下四个角度考虑：  
**1. 状态定义  
2. 状态间的转移方程定义  
3. 状态的初始化  
4. 返回的结果**

状态定义的要求：**定义的状态一定要形成递推关系**。

一句话概括：三特点四要素本质

适用场景：最大值/最小值。可不可行。是不是，方案个数。

递归的思想还是要从实际问题切入来理解，

# 二、斐波那契数列 #

这道题是剑指Offer的一道题，非常经典

描述

大家都知道斐波那契数列，现在要求输入一个整数n，请你输出斐波那契数列的第n项（从0开始，第0项为0，第1项是1）。  
 n ≤ 39 n ≤ 39 n\\leq 39n≤39 n≤39n≤39

[斐波那契数列][Link 1]

## 2.1 递归解法 ##

首先，递归解法很容易理解，但是递归对n有很大的要求，太大会导致栈帧溢出，究其原因是每次返回的都是两个函数的递归，随着n的增大造成指数级增长。

class Solution {
        
    public:
        int Fibonacci(int n) {
        
            if(n == 0)
                return 0;
            if(n == 1 || n ==2)
                return 1;
            return Fibonacci(n - 1) + Fibonacci(n - 2);
        }
    };

这道题递归解法空间复杂度是O(2^(n-1))，时间复杂度O(N)，这道题使用动规如何解呢？

## 2.2 动规解法 ##

我们列出四要素：

**问题：**  
数列第n项的值

**状态F(i)：**  
数列第i项的值

**转移方程：**  
 F ( i ) = F ( i − 1 ) + F ( i − 2 ) F(i) = F(i - 1) + F(i - 2) F(i)=F(i−1)\+F(i−2)  
**初始状态**至少有两项：  
F(0) = 0  
F(1) = 1  
**返回值**  
F(n)

我们可以用一个数组把中间某一项的值保存下来，后一项的值就等于前两项值之和

class Solution {
        
    public:
        int Fibonacci(int n) {
        
            //时间复杂度O（n）空间复杂度O(n)
            vector<int> F(n + 1, 0);    //定义数组保存每一次的状态值
            //初始化：F[0] = 0, F[1] = 1
            F[0] = 0;
            F[1] = 1;
            //状态方程求解F[i] = F[i - 1] + F[i - 2]
            for(int i = 2; i <= n; ++i)
            {
        
                F[i] = F[i - 1] + F[i - 2];
            }
            return F[n];
    };

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMDc2MDIy_size_16_color_FFFFFF_t_70]  
这道题时间复杂度O（n），空间复杂度O(n)，依然可以继续优化

## 2.3 迭代解法 ##

class Solution {
        
    public:
        int Fibonacci(int n) {
             
            //时间复杂度O(n),空间复杂度是O(1)
            //fn1代表f(n - 1), fn2代表f(n - 2)
            int fn1 = 1;
            int fn2 = 0;
            int fn;
            if(n <= 1)
                return n;
            for(int i = 2; i <=n; ++i)
            {
        
                fn = fn1 + fn2;
                fn2 = fn1;
                fn1 = fn;
            }
            return fn;
        }
    };

通过迭代，这道题时间复杂度O(n),空间复杂度是O(1)

[Link 1]: https://www.nowcoder.com/practice/c6c7742f5ba7442aada113136ddea0c3
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMDc2MDIy_size_16_color_FFFFFF_t_70]: /images/20221005/9888a012ce3147af93f95ac33d3516ca.png