leetcode刷题笔记 1137.第 N 个泰波那契数

题目描述

泰波那契序列 Tn 定义如下：

T0 = 0, T1 = 1, T2 = 1, 且在 n >= 0 的条件下 Tn+3 = Tn + Tn+1 + Tn+2

给你整数 n，请返回第 n 个泰波那契数 Tn 的值。

题目分析

本道题与leetcode 509、斐波那契数很相似[leetcode刷题笔记 leetcode刷题笔记 509、斐波那契数（Java语言实现）通过代码随想录老哥分享的动态规划问题分析五步曲

1、确定dp数组（dp table）以及下标的含义
2、 确定递推公式
3、 dp数组如何初始化
4、 确定遍历顺序
5、举例推导dp数组（debug）

我们来分析一下这个问题。
1、确定dp数组（dp table）以及下标的含义

观察题目，dp[i]的含义应为第i位的泰波那契序列的值，同时下标i应为泰波那契序列的的序列数。

2、 确定递推公式

dp[i] = dp[i-3]+dp[i-2]+dp[i-1];

3、 dp数组如何初始化

dp[0],dp[1],dp[2]无法从递推公式中得出，故而自行初始化作为边界条件。

4、确认遍历顺序

由前向后

5、举例推导dp数组

debug用

代码实现

class Solution {
    public int tribonacci(int n) {
        int t[] = new int [n+1];
        if(n==0)
            return 0;
        if(n==1)
            return 1;
        if(n==2)
            return 1;
        t[0]=0;
        t[1]=1;
        t[2]=1;
        for(int i=3;i<=n;i++){
            t[i]=t[i-1]+t[i-2]+t[i-3];
        }
        return t[n];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

根据状态转移方程和边界条件，可以得到时间复杂度和空间复杂度都是 O(n)O(n) 的实现。由于 T(n)T(n) 只和前三项有关，因此可以使用「滚动数组思想」将空间复杂度优化成 O(1)O(1)。如下的代码中给出的就是这种实现。

class Solution {
    public int tribonacci(int n) {
        if (n == 0) {
            return 0;
        }
        if (n <= 2) {
            return 1;
        }
        int p = 0, q = 0, r = 1, s = 1;
        for (int i = 3; i <= n; ++i) {
            p = q;
            q = r;
            r = s;
            s = p + q + r;
        }
        return s;
    }
}


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20