题目描述泰波那契序列 Tn 定义如下T0 0, T1 1, T2 1, 且在 n 0 的条件下 Tn3 Tn Tn1 Tn2给你整数 n请返回第 n 个泰波那契数 Tn 的值。示例 1输入n 4输出4解释T_3 0 1 1 2T_4 1 1 2 4示例 2输入n 25输出1389537算法原理这是一道使用动态规划解决的题目所以按照 5 步来进行处理创建一个 dp 数组确定状态表示状态表示指 dp 数组第 i 个元素代表着什么在这道题目里第 i 个元素dp[i]dp[i]dp[i]代表了第 i 个泰波那契数TiT_iTi​确定状态转移方程指第 i 个泰波那契数TiT_iTi​的计算方式题目中给出的是Ti3TiTi1Ti2T_{i3} T_i T_{i1} T_{i2}Ti3​Ti​Ti1​Ti2​只要让 i 减去 3就可以得到TiTi−1Ti−2Ti−3T_{i} T_{i-1} T_{i-2} T_{i-3}Ti​Ti−1​Ti−2​Ti−3​也就是说dp[i]dp[i−1]dp[i−2]dp[i−3]dp[i] dp[i - 1] dp[i - 2] dp[i - 3]dp[i]dp[i−1]dp[i−2]dp[i−3]初始化用来保证计算时数组不越界如果 i 0dp[0]dp[−1]dp[−2]dp[−3]dp[0] dp[-1] dp[-2] dp[-3]dp[0]dp[−1]dp[−2]dp[−3]这是会越界的dp[1],dp[2]dp[1], dp[2]dp[1],dp[2]在计算时也是一样所以要先初始化这三个值。题目中已经给出dp[0]T00dp[1]T11dp[2]T22dp[0] T_0 0dp[1] T_1 1dp[2] T_2 2dp[0]T0​0dp[1]T1​1dp[2]T2​2填表顺序由于新算出来的值依赖于之前的三个值所以填表是从左向右的返回值题目要得到第 n 个泰波那契数的值所以返回dp[n]dp[n]dp[n]代码classSolution{public:inttribonacci(intn){intdp[38]{0};dp[0]0,dp[1]1,dp[2]1;for(inti3;in;i){dp[i]dp[i-1]dp[i-2]dp[i-3];}returndp[n];}};空间优化以计算第 5 个泰波那契数T57T_5 7T5​7为例当计算出T32T_3 2T3​2计算T44T_4 4T4​4时可以发现只需要用到T1,T2,T3T_1, T_2,T_3T1​,T2​,T3​。T00T_0 0T0​0已经不需要使用了。因此每当计算出一个泰波那契数的时候之前算出来过的一个数就可以丢弃了在这样的条件下不需要使用一个数组来保存得到的所有泰波那契数只要用三个变量 a, b, c 保存计算TiT_iTi​时需要的数Ti−1,Ti−2,Ti−3T_{i-1}, T_{i-2}, T_{i-3}Ti−1​,Ti−2​,Ti−3​即可优化后的代码classSolution{public:inttribonacci(intn){if(n0)return0;elseif(n1||n2)return1;inta0,b1,c1,d0;for(inti3;in;i){dabc;ab;bc;cd;}returnd;}};