企业官网建设流程全解析

1137. 第 N 个泰波那契数 - 力扣（LeetCode）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 = 2T_4 = 1 + 1 + 2 = 4示例 2：输入：n = 25输出：1389537 提示： * 0 <= n <= 37 * 答案保证是一个 32 位整数，即 answer <= 2^31 - 1。https://leetcode.cn/problems/n-th-tribonacci-number/

题目简介

泰波那契序列 Tₙ 定义：

• T₀ = 0，T₁ = 1，T₂ = 1
• n ≥ 3 时，Tₙ = Tₙ₋₁ + Tₙ₋₂ + Tₙ₋₃

给定整数n，返回第n个泰波那契数。

泰波那契数可以理解为三项版斐波那契数列，是动态规划非常经典的入门练习题。

动态规划五步

做 DP 题我习惯按这五步思考，不容易漏条件：

1. dp 数组含义：dp[i]表示第i个泰波那契数的值
2. 状态转移方程：dp[i] = dp[i-1] + dp[i-2] + dp[i-3]
3. dp 数组初始化：dp[0]=0，dp[1]=1，dp[2]=1
4. 遍历顺序：从小到大正向遍历，后面的值依赖前面已经计算完成的值
5. 返回结果：dp[n]

class Solution { public: int tribonacci(int n) { // 定义dp[],有关dp[]的方程,初始化,从哪个方向开始填,返回值 if(n == 0) return 0; if(n == 1 || n == 2) return 1; vector<int> dp(n + 1); dp[0] = 0; dp[1] = 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]; } };

我们还可以在此基础上添加对于空间上的优化

因为实际上用的dp[i]的求值只与前面三个有关,就不需要存储那么多;