[数据结构与算法]动态规划（一）

509. 斐波那契数

斐波那契数，通常用 F(n) 表示，形成的序列称为 斐波那契数列 。该数列由 0 和 1 开始，后面的每一项数字都是前面两项数字的和。也就是：

F(0) = 0，F(1) = 1
F(n) = F(n - 1) + F(n - 2)，其中 n > 1
给你 n ，请计算 F(n) 。
示例 1：

输入：2
输出：1
解释：F(2) = F(1) + F(0) = 1 + 0 = 1

示例 2：

输入：3
输出：2
解释：F(3) = F(2) + F(1) = 1 + 1 = 2

示例 3：

输入：4
输出：3
解释：F(4) = F(3) + F(2) = 2 + 1 = 3

代码如下：

class Solution {
public:

/* 一. 递归算法  ,时间复杂度o(2^n)
    int fib(int n) {
        if(n<=1)
        {
            return n;
        }
        else
        {
            return fib(n-1)+fib(n-2);
        }
    }
    */
    // 二. for循环方法  , 时间复杂度o(n)
    int fib(int n)
    {
        if(n<=1)
        {
            return n;
        }
        int attr[n+1];
        attr[0] = 0;
        attr[1] = 1;
        for(int i=2;i<=n;i++)
        {
            attr[i] = attr[i-1]+ attr[i-2];
        }

        return attr[n];

    }
};
    

1137. 第 N 个泰波那契数

泰波那契序列 Tn 定义如下：

T0 = 0, T1 = 1, T2 = 1, 且在 n >= 0 的条件下 Tn+3 = Tn + Tn+1 + Tn+2

给你整数 n，请返回第 n 个泰波那契数 Tn 的值。

示例 1：

输入：n = 4
输出：4
解释：
T_3 = 0 + 1 + 1 = 2
T_4 = 1 + 1 + 2 = 4

示例 2：

输入：n = 25
输出：1389537

代码如下：

class Solution {
public:

    // 一. 使用递归，时间复杂度为o(2^n)
    int tribonacci(int n)
    {
        if(n==0)
        {
            return 0;
        }
        else if(n<=2)
        {
            return 1;
        }
        else{
            return tribonacci(n-3)+tribonacci(n-2)+tribonacci(n-1);
        }
    }
/*

    // 二. 使用for 循环，时间复杂度o(n)
    int tribonacci(int n) {
        if(n==0)
        {
            return 0;
        }
        else if(n==1)
        {
            return 1;
        }
        else if(n==2)
        {
            return 1;
        }
        int attr[n+1];
        attr[0] = 0;
        attr[1] = 1;
        attr[2] = 1;
        for(int i=3;i<=n;i++)
        {
            attr[i] = attr[i-1]+attr[i-2]+attr[i-3];
        }
        return attr[n];

    }*/
};