坚持就是胜利 - - 

1.第N个泰波那切数

2.三步问题

3.使用最小花费爬楼梯

4.解码方法

力扣链接：力扣

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

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

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

 首先我们分析一下题目，在n>=0的条件下也就是说都是正数，然后给了一个算泰博纳妾数的公式，这道题很简单，但是我们还是一步步带着大家来分析：

首先在我们以后做动态规划的题，都按照一下这个模板来编写：

1.状态表示

首先我们先把公式重新推导一下，让每边减3得到Tn = Tn-3 + Tn-2 + Tn-1 ，Tn就是第n个泰博纳妾数，根据前三个泰波纳妾数推导出来的第n个，所以说dp[i]的状态就是第i个泰波纳妾数

2.状态转移方程

dp[i] = dp[i-1] + dp[i-2] + dp[i-3]    因为第i个泰波纳妾数等于前三个泰波纳妾数的和，所以转移方程就是这个

3.初始化

我们初始化的目的是为了防止越界，如下图：

第0个泰波那切数的前三个都是非法的，所以我们必须给定第0个泰波纳妾数，同理dp[1]和dp[2]同样会越界，而题目又贴心的给了我们初始值，dp[0] = 0,dp[1] = 1,dp[2] = 1 

4.填表以及确定填表顺序

因为我们是知道左边的值，依靠左边的值推出来右边的值，所以顺序是从左向右

5.返回值

既然让我们返回第n个泰波纳妾数，而我们的状态表示dp[i]就表示第i个泰波纳妾数，所以返回dp[n]就是第n个泰波纳妾数

思路理解了我们直接写代码：

取楼顶-1台阶的最小值和楼顶-2台阶的最小值相比较，最小的就是到楼顶的最小值，所以刚刚的实例2答案为15.

1.状态表示

dp[i]表示到达第i个台阶的最小花费

2.状态转移方程

dp[i] = min(dp[i-1]+cost[i-1],dp[i-2]+cost[i-2])

3.初始化

因为题目告诉了从第0个台阶或者第1个台阶开始爬，所以之前到达0或1台阶的最小花费是0，所以dp[0]和dp[1]都等于0

4.填表

5.返回值

由于数组是从0开始的，size()的大小就是楼顶的位置，所以返回dp[size()]即可。