企业官网建设流程全解析

题目链接：1137. 第 N 个泰波那契数

题目解析

动态规划（Dynamic programming，简称 DP）是一种通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法，在查找有很多重叠子问题的情况的最优解时有效。它将问题重新组合成子问题。为了避免多次解决这些子问题，它们的结果都逐渐被计算并被保存，从简单的问题直到整个问题都被解决。因此，动态规划保存递归时的结果，因而不会在解决同样的问题时花费不必要的时间。

通常的解决步骤有五步：

1. 确定状态表示/dp表的含义
2. 确定状态转移方程/递推公式
3. 初始化
4. 确定填表顺序
5. 确定返回值

题目给出泰波那契序列Tn定义如下：

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

并且给出一个整数n，我们需要返回第n个泰波那契数Tn的值。

根据题目所给条件，我们可以得到Tn = Tn-3 + Tn-2 + Tn-1，即第 n 个泰波那契数 Tn 的值是其前面三个数之和。

例1：n = 4

可以看到，第 4 个泰波那契数是 4，因此返回4。

算法原理

确定状态表示

状态表示/dp表含义可以从题目要求找出，也可以从重复子问题中找出。

根据题目，我们可以直接确定：dp[i] 表示第 N 个泰波那契数的值。

确定状态转移方程

题目给出一个条件：在 n >= 0 的条件下Tn+3 = Tn + Tn+1 + Tn+2，这直接就可以让我们得出状态转移方程。

根据题目的条件得到Tn = Tn-3 + Tn-2 + Tn-1，则状态转移方程：dp[i] = dp[i-3] + dp[i-2] + dp[i-1]。

初始化

根据状态转移方程dp[i] = dp[i-1] + dp[i-2] + dp[i-3]，我们可以计算所有 i >= 3 的 dp 值，但是当 i 为 0、i 为 1、i 为 2 时，就会越界访问。

题目也给出条件T0 = 0，T1 = 1，T2 = 1，于是我们就得到dp[0] = 0，dp[1] = dp[2] = 1这三个初始化条件。

确定填表顺序

假如我们此时只知道 n 为 0、1、2 时对应的泰波那契数，需要求第 4 个泰波那契数，能直接代入状态转移方程dp[i] = dp[i-1] + dp[i-2] + dp[i-3]求解吗？

答案是不行的，因为状态转移方程告诉我们，必须要在前三个数都已知的情况下才可以代入求解，而在这个例子里，我们还没有求解第 3 个泰波那契数，因此无法直接计算第 4 个泰波那契数，必须先计算第 3 个泰波那契数才行，这就是 dp 表的填表顺序，本题是从左往右的顺序。

确定返回值

本题的返回值题干已经告诉我们了：返回第n个泰波那契数Tn的值，也就是dp[n]。

细节问题

1. 考虑边界情况：n == 0 时怎么处理？n 为 1 或者 2 时又怎么处理？
2. 本题需要访问下标为n的数，因此开辟 dp 数组的时候大小应是n+1。

空间优化

在动态规划的一类特定问题中，通常可以进行空间优化，主要是以滚动数组来代替 dp 表，减少了空间内存的消耗。

状态转移方程由dp[i] = dp[i-1] + dp[i-2] + dp[i-3]改为d = a + b + c，开始之前将 a 初始化为 0、b 和 c 初始化为 1。

我们只需要将 a、b、c 三个变量轮番赋值更新，就可以不断地算出下一个泰波那契数，其中赋值更新的语句必须按照如下的顺序：

1. a = b
2. b = c
3. c = d

代码实现

普通版本

classSolution{publicinttribonacci(intn){// 边界情况if(n==0){return0;}if(n==1||n==2){return1;}int[]dp=newint[n+1];// 初始化dp[0]=0;dp[1]=dp[2]=1;// 填表:从左往右for(inti=3;i<=n;i++){dp[i]=dp[i-1]+dp[i-2]+dp[i-3];}// 返回结果returndp[n];}}

空间优化版本

classSolution{publicinttribonacci(intn){inta=0,b=1,c=1;// 边界情况if(n==0){returna;}if(n==1||n==2){returnb;}intd=0;for(inti=3;i<=n;i++){d=a+b+c;a=b;b=c;c=d;}// 返回结果returnd;}}

完