【LeetCode】--- 动态规划 集训（一）

一、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];}
};