第 N 个泰波那契数

亦凉 2024-03-16 21:09 84阅读 0赞

## 1. 题目分析 ##

题目链接来自力扣 : [第 N 个泰波那契数][N]  
![image.png][]  
运用一点小技巧, 当 Tn+3 = Tn + Tn+1 + Tn+2 同时减去 3 时, 则变成了一个我们熟悉的式子.  
**Tn = Tn-3 + Tn-2 + Tn-1**  
已知条件为： T0 = 0, T1 = 1, T2 = 1, 带入这个式子, 分析条件 :  
n = 3 时, T3 = T0 + T1 + T2 = 0 + 1 + 1 = 2  
n = 4 时, T4 = T1 + T2 + T3 = 1 + 1 + 2 = 4  
n = 5 时, T5 = T2 + T3 + T4 = 1 + 2 + 4 = 7  
…

## 2. 状态表示 ##

根据题目要求, 计算第 n 个泰波那契数的值. 因此我们在这定义一个 dp\[n + 1\] 的一维数组. dp\[i\] 含义则为下标为第 i 个位置时, 对应的泰波那契数的值.

**为什么定义一个大小为 n + 1 的 dp 数组呢 ?**  
**原因在于我们需要求解第 n 这个位置处的泰波那契数的值, 如果定义为 dp\[n\], 下标最多访问到 n - 1, 无法计算 dp\[n\] 的值, 会越界不满足题目需求.**  
![image.png][image.png 1]

## 3. 状态转移方程 ##

如何确定一个状态方程呢 ? 对于状态表示为一个一维的 dp 表(dp 数组)时,**一般采取用最近的表达式**  
**怎么理解这个最近的表达式 ?**  
下标 3 位置的泰波那契数为下标 0 1 2 位置的值之和  
下标 4 位置的泰波那契数为下标 1 2 3 位置的值之和  
下标 5 位置的泰波那契数为下标 2 3 4 位置的值之和  
…  
这里表示某个下标位置时, 采取的前面三个下标位置则为最近的位置, 他们之间的关系则为最近表达式.

根据上面我们对题目的分析, 发现 **Tn = Tn-3 + Tn-2 + Tn-1 , 而Tn 表示的是第 n 个位置时, 对应的泰波那契数的值. 对应到我们的状态表示中即为 dp\[i\] . 同理 其他位置分别为dp\[i-1\], dp\[i-2\], dp\[i-3\]… 分别对应我们的 T\[n-1\], T\[n-2\], T\[n-3\].**

最终我们的状态转移方程为 :  
**dp\[i\] = dp\[i - 1\] + dp\[i - 2\] + dp\[i - 3\]**  
**当我们把这个 dp 表(也就是 dp 数组) 的每个下标的位置填完了, 里面的某一项就可能是我们需要的答案.**

## 4. 初始化 ##

为什么需要进行初始化呢 ? 最主要就是防止 dp 数组越界  
当我们求解 dp\[2\] 时, dp\[2\] = dp\[1\] + dp\[0\] + dp\[-1\], 很显然 dp\[-1\]是越界了的. **为了防止计算时越界, 需要根据题目要求提前进行初始化.**  
上面说到, T0 也就是对应 dp\[0\], T1 的值也就对应 dp\[1\], T2 的值也就对应 dp\[2\], T3的值也就对应 dp\[3\]. 也就是说, 我们的 dp\[0\] = 0, dp\[1\] = 1, dp\[2\] = 1;  
dp\[4\] 依赖前面三个下标的值之和. dp\[5\]依赖前面三个下标值之和. 这样就可以计算出一直到 i 下标的所有值, 也就可以填满dp表了.

## 5. 填表顺序 ##

对于 dp 表该如何, 是存在一个方向问题的. 从后向前填写还是从前向后填写需要根据之前的 " 依赖关系 " . 例如 dp\[4\] 就需要前面三项之和, 也就是说必须计算前面三个下标的值才能计算出dp\[4\]. 因此我们这里的填表顺序为从左往右

## 6. 返回值 ##

返回值的确定, 一般根据题目要求以及状态表示  
题目中, 要求返回第 n 个位置时的泰波那契数. n 位置则对应我们状态表示中 dp 数组的 n 下标. 它的值 Tn 也就对应 dp\[n\] 的值. 因此返回 dp\[n\] 这个位置的值则为第 n 个位置时对应的泰波那契数.

## 7. 代码演示 ##

虽然最后直接返回 dp\[n\] 可以表示 n 为 0 , 1 , 2 时候的情况. 但是还是要做一下特殊处理较好.

class Solution {
        
        public int tribonacci(int n) {
        
    
            // 处理边界值
            if(n == 0) return 0;
            if(n == 1 || n == 2) return 1;
    
            // 1. 创建 dp 表
            int[] dp = new int[n + 1];
    
            // 2. 初始化
            dp[0] = 0;
            dp[1] = dp[2] = 1;
    
            // 3. 填写 dp 表
            for(int i = 3; i <= n; i++) {
        
                // 根据状态转移方程填写 dp 表
                dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3];
            }
    
            // 4. 确定返回值
            return dp[n];
        }
    }

[N]: https://leetcode.cn/problems/n-th-tribonacci-number/
[image.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/7c5151982d22491780adf053c80aa4cb.png
[image.png 1]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/6d7b2b32bc8e48e284a5eedae955f27b.png