LeetCode-1137. 第 N 个泰波那契数

旧城等待， 2024-03-24 14:55 43阅读 0赞

#### 目录 ####

*   *  动态规划

题目来源  
[1137. 第 N 个泰波那契数][1137. _ N]

### 动态规划 ###

动规五部曲：

*  1.确定dp数组以及下标的含义

dp\[i\]的定义为：第i个数的泰波那契数值是dp\[i\]

*  2.确定递推公式

题目已经把递推公式直接给我们了：Tn+3 = Tn + Tn+1 + Tn+2  
状态转移方程 dp\[i\] = dp\[i-1\] + dp\[i-2\] + dp\[i-3\];

*  3.dp数组如何初始化

题目中把如何初始化也直接给我们了，如下：

dp[0] = 0;
    dp[1] = 1;
    dp[1] = 1;

*  4.确定遍历顺序

从递归公式dp\[i\] = dp\[i - 1\] + dp\[i - 2\] + dp\[i-3\];中可以看出，dp\[i\]是依赖 dp\[i - 1\] 和 dp\[i - 2\] 和 dp\[i - 3\]，那么遍历的顺序一定是从前到后遍历的

*  5.举例推导dp数组

按照这个递推公式dp\[i\] = dp\[i - 1\] + dp\[i - 2\] + dp\[i-3\];，我们来推导一下，当N为4的时候，dp数组应该是如下的数列：  
0 1 1 2 4

class Solution {
        
        public int tribonacci(int n) {
        
            int[] dp = new int[n+1];
            if(n == 0){
        
                return dp[0] = 0;
            }
            if(n == 1 || n == 2){
        
                return 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];
        }
    }

![在这里插入图片描述][3e145dee8dff424fbcf65ede02373ad7.png]

[1137. _ N]: https://leetcode.cn/problems/n-th-tribonacci-number/
[3e145dee8dff424fbcf65ede02373ad7.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/24/3e56a9a4e2f74beb977ecdfdc626b00b.png