前言

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，不就是你想要的第五项了吗。以此类推，解决此题。

解题代码

classSolution {
publicinttribonacci(intn) {
if (n==0) {
return0;
        }
if (n<=2) {
return1;
        }
intp=0, q=0, r=1, s=1;
for (inti=3; i<=n; ++i) {
p=q;
q=r;
r=s;
s=p+q+r;
        }
returns;
    }
}