【动态规划篇】1137. 第 N 个泰波那契数

admin管理员组

文章数量:1037775

【动态规划篇】1137. 第 N 个泰波那契数

在这里插入图片描述

前言：

动态规划问题一般分为五步：

1. 先确定一个状态表示
2. 根据状态表示来推导状态方程
3. 初始化
4. 填表顺序
5. 返回值

①状态表示

• 先创建一个以为数组，起名为dp,这个一维数组就叫做dp表

• 把dp表填满，填满后的某个值就是我们想要的结果
• 状态表示是什么呢？dp表中某个值所表示的含义 。
• 怎么来的呢？ⓐ根据题目要求ⓑ经验+题目要求ⓒ分析题目过程中发现重复子问题

➁状态转移方程（即dp[i]是什么）

• 例如下面的这道题中的dp[i] = dp[i-1] + dp[i-2] + dp[i-3]

➂初始化

• 保证填表的时候不越界，dp[i] = dp[i-1] + dp[i-2] + dp[i-3]，所以前三个位置会越界
• 初始化 dp[0] = 0, dp[1] = dp[2] = 1

➃填表顺序

• 为了填写当前状态的时候，所需要的状态已经算过了

➄返回值

• 题目要求+状态表示

1137. 第 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

解题思路：

1. 状态表示 创建一个dp表，让dp表中dp[0]表示第0个泰波那契数，dp[1]表示第1个泰波那契数…dp[i]表示第i个泰波那契数
2. 状态转移方程 题目中为 Tn+3 = Tn + Tn+1 + Tn+2处理一下得 Tn = Tn-3 + Tn-2 + Tn-1,所以状态方程为dp[i] = dp[i-1]+ dp[i-2] + dp[i-3]
3. 初始化 dp[0] = 0,dp[1] = dp[2] = 1
4. 填表顺序 要求填4的时候3已经计算过了，所以填表顺序为从左向右
5. 返回值 返回dp[i]

代码实现：

代码语言：javascript代码运行次数：0运行复制

class Solution {
public:
    int tribonacci(int n) {
        //处理细节问题
        if(n==0) return 0;
        if(n==1||n==2) return 1; 

        vector<int> dp(n+1); //创建一个dp表
        dp[0] = 0,dp[1] = dp[2] = 1;//初始化
        for(int i = 3;i <= n;i++)
        dp[i] = dp[i-1] + dp[i -2] + dp[i - 3];

        return dp[n];
    }
};

时间复杂度：O(n) 空间复杂度：O(n)

动态规划空间优化 -滚动数组  求dp[4]的时候dp[0]相当于浪费空间，当我们求后面的某个值时，前面的有些值我们就不需要了，这个时候就可以用 滚动数组来优化。

abc求完d后，abc滚到下面 代码实现：

代码语言：javascript代码运行次数：0运行复制

class Solution {
public:
    int tribonacci(int n) {
        //处理细节问题
        if(n==0) return 0;
        if(n==1||n==2) return 1; 

        int a = 0,b = 1,c = 1,d = 0;
        for(int i = 3;i <= n;i++)
        {
            d = a + b + c;
            //滚动操作
            a = b;
            b = c;
            c = d;
        }
        return d;
    }
};

【动态规划篇】1137. 第 N 个泰波那契数

在这里插入图片描述

前言：

动态规划问题一般分为五步：

1. 先确定一个状态表示
2. 根据状态表示来推导状态方程
3. 初始化
4. 填表顺序
5. 返回值

①状态表示

• 先创建一个以为数组，起名为dp,这个一维数组就叫做dp表

• 把dp表填满，填满后的某个值就是我们想要的结果
• 状态表示是什么呢？dp表中某个值所表示的含义 。
• 怎么来的呢？ⓐ根据题目要求ⓑ经验+题目要求ⓒ分析题目过程中发现重复子问题

➁状态转移方程（即dp[i]是什么）

• 例如下面的这道题中的dp[i] = dp[i-1] + dp[i-2] + dp[i-3]

➂初始化

• 保证填表的时候不越界，dp[i] = dp[i-1] + dp[i-2] + dp[i-3]，所以前三个位置会越界
• 初始化 dp[0] = 0, dp[1] = dp[2] = 1

➃填表顺序

• 为了填写当前状态的时候，所需要的状态已经算过了

➄返回值

• 题目要求+状态表示

1137. 第 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

解题思路：

1. 状态表示 创建一个dp表，让dp表中dp[0]表示第0个泰波那契数，dp[1]表示第1个泰波那契数…dp[i]表示第i个泰波那契数
2. 状态转移方程 题目中为 Tn+3 = Tn + Tn+1 + Tn+2处理一下得 Tn = Tn-3 + Tn-2 + Tn-1,所以状态方程为dp[i] = dp[i-1]+ dp[i-2] + dp[i-3]
3. 初始化 dp[0] = 0,dp[1] = dp[2] = 1
4. 填表顺序 要求填4的时候3已经计算过了，所以填表顺序为从左向右
5. 返回值 返回dp[i]

代码实现：

代码语言：javascript代码运行次数：0运行复制

class Solution {
public:
    int tribonacci(int n) {
        //处理细节问题
        if(n==0) return 0;
        if(n==1||n==2) return 1; 

        vector<int> dp(n+1); //创建一个dp表
        dp[0] = 0,dp[1] = dp[2] = 1;//初始化
        for(int i = 3;i <= n;i++)
        dp[i] = dp[i-1] + dp[i -2] + dp[i - 3];

        return dp[n];
    }
};

时间复杂度：O(n) 空间复杂度：O(n)

动态规划空间优化 -滚动数组  求dp[4]的时候dp[0]相当于浪费空间，当我们求后面的某个值时，前面的有些值我们就不需要了，这个时候就可以用 滚动数组来优化。

abc求完d后，abc滚到下面 代码实现：

代码语言：javascript代码运行次数：0运行复制

class Solution {
public:
    int tribonacci(int n) {
        //处理细节问题
        if(n==0) return 0;
        if(n==1||n==2) return 1; 

        int a = 0,b = 1,c = 1,d = 0;
        for(int i = 3;i <= n;i++)
        {
            d = a + b + c;
            //滚动操作
            a = b;
            b = c;
            c = d;
        }
        return d;
    }
};

本文标签： 动态规划篇1137 第 N 个泰波那契数