一、第N个泰波那契数
泰波那契序列 Tn 定义如下：
T0 = 0, T1 = 1, T2 = 1, 且在 n >= 0 的条件下 Tn+3 = Tn + Tn+1 + Tn+2
给你整数 n，请返回第 n 个泰波那契数 Tn 的值。
对于一道动态规划类型的算法题，通常由以下几个步骤解题
算法原理
1.状态表示：创建一个dp表，用来存储所求得的数据。即dp[i]：第i个泰波那契数
2.状态转移方程：由题目给出的递推关系可以得出如下信息：
第N个数据是第N-1，N-2，N-3个数据的和，即dp[i]=dp[i-1]+dp[i-2]+dp[i-3];
3.dp表的初始化，要保证填表的时候，数据不会发生越界访问
由题意可得，dp[0] = 0,dp[1]=1,dp[2]=2;
4.填表顺序,保证填写当前状态的时候，所需要的状态已经计算出来
由状态转移方程可以知道本题的填表顺序是从左向右
5.返回值 由题目要求和状 态表示两部分可以推断出 本题的返回值是dp[n];
判断N是否会发生越界访问
编写代码
复杂度分析：上述解创建一个大小为N顺序表，故空间复杂度为O(N）
使用一次循环，时间复杂度是O(N)
下面介绍另外一种空间优化策略
通过分析上述解法我们可以发现，对于创建的dp表，每次只需用到四个数据的空间，所以可以选择滚动数组来优化空间；但是要注意迭代的顺序，具体可以参考下面的代码。
空间优化过的时间复杂度仍然是O(N)，但是空间复杂度是O(1)。
二、三步问题
三步问题。有个小孩正在上楼梯，楼梯有n阶台阶，小孩一次可以上1阶、2阶或3阶。实现一种方法，计算小孩有多少种上楼梯的方式。结果可能很大，你需要对结果模1000000007。
题意解析
1.状态表示：创建一个dp顺序表，dp[i]表示：到达i位置是共有多少种方法
2.状态转移方程: 以i位置最近的一步来划分问题，对于dp[i]，可以 从i-1级台阶跳一步上来，也可以从i-2ji级台阶跳两步上来，也可以从i-3级台阶跳三步上来。故有：
dp[i] = dp[i-1] + dp[i-2] + dp[i-3]，即到第i级台阶的方法是到 i-1，i-2, i-3级台阶的方法总和。
注意求解过程中可能会发生越界访问，要对求的数据进行取模
3.初始化，为了防止发生越界访问，要注意初始化的方法，通过以上分析可以发现，要对前三级台阶进行初始化，即：
dp[1] = 1, dp[2] = 2, dp[3] = 3
4.填表顺序，要保证填写当前状态时，所需要的状态已经计算过，此题的填表顺序是从左向右。
5.返回值：通过以上分析我们可以知道此题的返回值是dp[n]。
代码如下
时间复杂度是O(N),空间复杂度O(N)。
三、最小花费爬楼梯
给你一个整数数组 cost ，其中 cost[i] 是从楼梯第 i 个台阶向上爬需要支付的费用。一旦你支付此费用，即可选择向上爬一个或者两个台阶。你可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯。请你计算并返回达到楼梯顶部的最低花费。
题意解析
由题意可以得出一条隐含信息：对于大小为n的cost数组，cost[0]到cost[n-1]表示台阶花费，cost[n-1]的下一个位置才表示楼顶。
对于一个cost = [1,100,1,1,1,100,1,1,100,1]的数组，将从下标为 0 的台阶开始。
- 支付 1 ，向上爬两个台阶，到达下标为 2 的台阶。
- 支付 1 ，向上爬两个台阶，到达下标为 4 的台阶。
- 支付 1 ，向上爬两个台阶，到达下标为 6 的台阶。
- 支付 1 ，向上爬一个台阶，到达下标为 7 的台阶。
- 支付 1 ，向上爬两个台阶，到达下标为 9 的台阶。
- 支付 1 ，向上爬一个台阶，到达楼梯顶部。
总花费为 6 。
算法原理
解法一：以dp[i]为终点计算
1.状态表示：dp[i]表示到达i位置时的最小花费
2.状态转移方程：对与到达i位置的台阶有两种方法
第一种是从i-1的位置花费cost[i-1]向上爬一级台阶，到达i位置，花费dp[i-1]+cost[i-1]。
第二种是从i-2的位置花费cost[i-2]向上爬两级台阶，到达i位置，花费dp[i-2]+cost[i-2]。
因为do[i]要最小花费，故dp[i] = min(dp[i-1]+cost[i-1],dp[i-1]+cost[i-2])。取两者的最小值。
3.初始化，保证填表时不会发生越界访问
由状态转移方程可以知道需要初始化的数据是dp[0]和dp[1],即dp[0] = dp[1] = 0。
4.填表顺序，保证在计算i位置的状态时，所需要的其他位置的状态已经计算出来。
由状态转移方程可以知道，计算i位置时，需要使用到 i - 1 和 i - 2 的位置的数据，故此题的填表顺序是从左到右。
5.返回值，由题意知道此题要求的是到达楼顶的最下花费，故返回值是dp[n]。
代码如下
解法二：以dp[i]为起点计算
1.状态表示 dp[i]表示从i位置出发，到达楼顶的最小花费。
2.状态转移方程 因为每次只能向上爬一级或者两级台阶，所以dp[i]有两种情况
第一种:支付cost[i]，向上爬一级台阶，从i+1位置到达终点, dp[i+1]+cost[i]
第二种:支付cost[i],向上爬两级台阶，从i+2位置到达终点, dp[i+2]+cost[i]
所以有 dp[i] = min(dp[i+1], dp[i+2]) + cost[i];
3.初始化 有状态转移方程可以知道应该初始化后面的值，dp数组与cost数组同等规模即可
dp[n-1] = cost[n-1] dp [n-2] = cost[n -2].
4.填表顺序：有上述的状态转移方程可以知道，应该从右向左填表
5.返回值 应该返回dp[0] 和 dp[1]两者的最小值，即min(dp[0],dp[1])
时间复杂度是O(N)，空间复杂度是O(N)。
四、解码方法
题目解析
对于字符串s = "226"，它可以解码为 "BZ" (2 26), "VF" (22 6), 或者 "BBF" (2 2 6) ，共有三种解码方法。
算法原理
1.状态表示 dp[i]表示以i位置为结尾，所有的解码方法
2.状态转移方程 根据最近一步来划分问题，对与字符s[i]一共有两种解码方法
第一种 s[i]单独解码，（1）当1 <= s[i] <= 9时，解码成功，即在0 - i-1位置解码成功的所有字符后面加一个字符s[i]，所以有dp[i] = dp[i-1]。（2）当解码不成功时，因为i位置是最后一个字符了，所以整个字符串解码失败，返回-1。
第二种 s[i]与s[i-1]结合解码，（1）解码成功时，10 <= s[i-1]*10+s[i-1] <=26，即在0 -- i-2位置解码成功的所有字符串后面加一个字符，故有dp[i] = dp[i-2] 。（2）当解码不成功时，因为i位置是最后一个字符了，所以整个字符串解码失败，返回-1。
综上有 dp[i] = dp[i-1] + dp[i-2], 只有解码成功时才会加。
3.初始化 保证填表时不会越界，由状态转移方程可以知道应该初始化dp[0]和dp[1]。
dp[0] = 1，解码成功时，dp[0] = 0，解码不成功
dp[1] = 1 两个位置解码成一个字符，dp[1] = 2，两个位置分别单独解码成两个字符，
否则，两种情况都不存在时，dp[1] = 0。
4.填表顺序 由状态转移方程可以知道填表顺序应该是从左往右。
5.返回值 因为要解码到字符串的最后一个位置s[n-1]，所以要返回dp[n-1]。
编写代码
时间复杂度和空间复杂度都为O(N)。
优化处理 将初始化操作放在填表过程中，多开一个位置的空间，将整个数组统一往后移一个位置处理边界问题以及初始化操作
原始数组下标 s [ 0, 1, 2, 3, 4 ,......n-1]
旧dp表的下标 dp [0, 1, 2, 3, 4 ,......n-1], 将每个位置依次向后移动一位得到新dp表
新dp表的下标 dp [0, 1, 2, 3, 4 ,......n-1，n]
注意事项：
1.虚拟节点里的值要保证后面的填表是正确的，
在此题中，如果s[1]与s[2]一起解码成功，由递推关系dp[i] += dp[i-2]; 有dp[2] += dp[0]; 所以 dp[0] 应该初始化为1。
2.原始字符串与新dp表的下标映射关系
优化后的代码
