目录
一、1137. 第 N 个泰波那契数
题目地址： 1137. 第 N 个泰波那契数
泰波那契序列
Tn定义如下：
T0 = 0, T1 = 1, T2 = 1, 且在n >= 0的条件下Tn+3 = Tn + Tn+1 + Tn+2
给你整数n，请返回第n个泰波那契数Tn的值。
示例 1：
输入：n = 4
输出：4
解释：
T_3 = 0 + 1 + 1 = 2
T_4 = 1 + 1 + 2 = 4
示例 2：
输入：n = 25
输出：1389537
1.1 题目解析
因为要求的是第n个泰波那契序列，所以我们可以创建一个长度为 n 的dp表，用来表示第i位置的泰波那契序列（即：dp[i]表示：第 i 个泰波那契序列的值）。
接下来便是初始化，因为 dp[i]位置是前三个数的和，所以为了后序填表时不越界，要先初始化前三个数。题目中已给出前三个值，完成初始化即可（dp[0] = 0; dp[1] = dp[2] = 1;）。
填表顺序是：从左到右，依次填表。从下标为 3 的位置开始填表。
返回值为：dp[n]，即第 n 个位置的泰波那契序列的值。还需要注意的小细节是，当序列长度不足 3 时，要单独判断返回值。
1.2 状态转移方程
依据题目要求（已给出）：dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3];
1.3 解题代码
class Solution
{
public:
int tribonacci(int n)
{
//1. 创建dp表
//2. 初始化
//3. 填表
//4. 返回结束
if(n == 0) return 0;
if(n == 1 || n == 2) return 1;
vector<int> dp(n + 1);
dp[0] = 0, dp[1] = dp[2] = 1;
for(int i = 3; i <= n ; ++i)
dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3];
return dp[n];
}
};
二、面试题 08.01. 三步问题
题目地址： 面试题 08.01. 三步问题
三步问题。有个小孩正在上楼梯，楼梯有n阶台阶，小孩一次可以上1阶、2阶或3阶。实现一种方法，计算小孩有多少种上楼梯的方式。结果可能很大，你需要对结果模1000000007。
示例1:
输入：n = 3
输出：4
说明: 有四种走法
示例2:
输入：n = 5
输出：13
2.1 题目解析
为了求到第 n 级台阶的方法数，可以定义一个长度为 n+1 的dp表，dp[i]表示：到 i 位置时，一共有多少种方法。
状态转移方程的确立，因为小孩可以一次走一级，两级或三级台阶，所以他可以从第 n-1, n-2 或 n-3 级台阶上到第 n 级台阶。所以到第 n 级台阶的总方法数，是到上述三种台阶的方法数总和。（以 i 位置的状态，最近的一步，来划分问题）
接下来便是初始化，为了在填 dp 表时不越界（即取dp[i - 3]时），所以需要初始化前三个状态表的值（dp[1] = 1, dp[2] = 2, dp[3] = 4;）。还可以再多开一个位置，使台阶序号和 dp 表对应。
填表顺序：从左到右依次填表，从下标为 4 的位置开始填。
返回值：返回 dp[n]，即到第 n 级台阶的方法数。在 n <= 3 时要单独判断，因为状态表从下标为 4 位置开始判断（利用最近的前三个状态）
2.2 状态转移方程
依据题目要求：dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3];。还需要注意的是为了防止越界，顺应题目要求，要对结果模1000000007。那么便可写成如下格式：dp[i] = ((dp[i - 1] + dp[i - 2]) % num + dp[i - 3]) % num;
2.3 解题代码
class Solution
{
public:
int waysToStep(int n)
{
//1. 创建dp表
//2. 初始化
//3. 填表
//4. 返回结束
if(n == 1 || n == 2) return n;
if(n == 3) return 4;
vector<int> dp(n + 1);
dp[1] = 1, dp[2] = 2, dp[3] = 4;
int num = 1e9 + 7;
for(int i = 4; i <= n; ++i)
dp[i] = ((dp[i - 1] + dp[i - 2]) % num + dp[i - 3]) % num;
return dp[n];
}
};
三、746. 使用最小花费爬楼梯
题目地址： 746. 使用最小花费爬楼梯
给你一个整数数组 cost ，其中 cost[i] 是从楼梯第 i 个台阶向上爬需要支付的费用。一旦你支付此费用，即可选择向上爬一个或者两个台阶。
你可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯。
请你计算并返回达到楼梯顶部的最低花费。
示例 1：
输入：cost = [10,15,20]
输出：15
解释：你将从下标为 1 的台阶开始。
- 支付 15 ，向上爬两个台阶，到达楼梯顶部。
总花费为 15 。
示例 2：
输入：cost = [1,100,1,1,1,100,1,1,100,1]
输出：6
解释：你将从下标为 0 的台阶开始。
- 支付 1 ，向上爬两个台阶，到达下标为 2 的台阶。
- 支付 1 ，向上爬两个台阶，到达下标为 4 的台阶。
- 支付 1 ，向上爬两个台阶，到达下标为 6 的台阶。
- 支付 1 ，向上爬一个台阶，到达下标为 7 的台阶。
- 支付 1 ，向上爬两个台阶，到达下标为 9 的台阶。
- 支付 1 ，向上爬一个台阶，到达楼梯顶部。
总花费为 6 。
3.1 题目解析
此题所求的是达到楼梯顶部的最低花费，那么我们便可定义一个长度为 n+1 的 dp 状态表。多开一个是因为，此处的楼梯顶部，不是数组cost.size()，而是最后一个位置的下一个。那么我们便可使用，dp[i]来表示：到达 i 位置时，最小花费。
状态转移方程的确立，可以根据最小花费，因为一次可以向上爬一个或两个台阶。那么到达第 i 级台阶的最小花费，便可用最近的状态推导 dp[i]。即：1. 先到达 i - 1位置，然后支付cost[i - 1]，走一步(dp[i - 1] + cost[i - 1])； 2. 先到达 i - 2位置，然后支付cost[i - 2]，走两步(dp[i - 2] + cost[i - 2])。然后求两者最小值，这便是到达第 i 级台阶的最小费用。
初始化：为了后序填表不越界，且初始化的值不影响填表，所以可将前两个状态初始化为0(dp[0] = dp[1] = 0;)。
填表顺序：从左到右，依次填表。从下标为 2 的位置开始填。
返回值：dp[n]即是到达楼梯顶部的最低费用。
3.2 状态转移方程
依据题目要求：dp[i] = min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i -2]);
3.3 解题代码
class Solution
{
public:
int minCostClimbingStairs(vector<int>& cost)
{
//1. 创建dp表
//2. 初始化
//3. 填表
//4. 返回结束
int n = cost.size();
vector<int> dp(n + 1);
dp[0] = 0, dp[1] = 0;
for(int i = 2; i <= n; ++i)
dp[i] = min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]);
return dp[n];
}
};
