第 N 个泰波那契数

简介: 第 N 个泰波那契数

1. 题目分析



题目链接来自力扣 : 第 N 个泰波那契数

a78274372e9f833e3f75a44977b195cf.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] 的值, 会越界不满足题目需求.

6840f2a966cf1c41d0a9f0e54e012f91.png


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];
    }
}



相关文章
|
7月前
|
C++
第 N 个泰波那契数(C++)
第 N 个泰波那契数(C++)
43 0
|
6月前
蓝桥杯动态规划-第五弹 最大子数组和 买卖股票最佳时机IV 第N个泰波那契数 环形数组
蓝桥杯动态规划-第五弹 最大子数组和 买卖股票最佳时机IV 第N个泰波那契数 环形数组
|
7月前
|
存储
每日一题啦(● ̄(エ) ̄●)(尼克切斯定理,等差数列)
每日一题啦(● ̄(エ) ̄●)(尼克切斯定理,等差数列)
31 0
|
算法
【学会动态规划】第 N 个泰波那契数(1)
【学会动态规划】第 N 个泰波那契数(1)
117 1
|
算法 Windows
算法简单题,吾辈重拳出击 - 第 N 个泰波那契数
听说过斐波那契数列,那你听说过泰波那契数列吗?
|
机器学习/深度学习 算法
【刷穿 LeetCode】第 N 个泰波那契数 :「迭代」&「递归」&「矩阵快速幂」&「打表」
【刷穿 LeetCode】第 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   提示: 0 <= n <= 37 答案保证是一个 32 位整数,即 answer <= 2^31 - 1。 来源:力扣(LeetCode) 链接:leetcode-cn.com/
Indivisibility——容斥原理的应用
题目描述 给一个数n,找出1 ~ n 范围内不被 2 ~ 10整除的数的个数
102 0
|
算法 Java C语言
LeetCode刷题1137-第n个泰波那契数-
LeetCode刷题1137-第n个泰波那契数-
140 0
LeetCode刷题1137-第n个泰波那契数-
|
机器学习/深度学习
LeetCode 训练场:1137. 第 N 个泰波那契数
LeetCode 训练场:1137. 第 N 个泰波那契数
98 0