Leetcode 06——第N个泰波那契数（Java）

Algorithms + Data Structures = Programs.

                                                      ————Pascal之父 Nicklaus Wirth

算法 + 数据结构 = 程序

坚持刷算法题，变得更强！

（如果对你有帮助的话，可以帮忙点赞一下哦）

我们先来看一下题目要求：给了我们泰波那契数列的前三项，然后给了我们一个公式，告诉我们之后的项的值根据公式来计算，很明显，我们可以和做数学题一样，一个数一个数加起来得出我们的结果。但这种解题方式的底层就和数组或者说顺序表很类似。

此题比较简单，求过去的前三项之和就行，关键在于怎么动态实现一个数组内部的数值变化，当然数组只是一种考虑方式，我们可以直接用变量来实现。见下图。

 题目中给了你泰波那契数前三项，0，1，1。那么从第四项开始我们就要计算他的值了。

思路如下：

p,q,r,s四个变量用来存放数值，s = p+q+r，即s存放和，那么你会疑问第五项呢？第五项不就是泰波那契数列第2,3,4项的和了吗？  问得好，那我们把计算好的s值给r，r原来的值给q，q原来的值给p，然后再s = p+q+r，不就是你想要的第五项了吗。以此类推，解决此题。

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