一、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]
即是到达楼梯顶部的最低费用。文章来源:https://www.toymoban.com/news/detail-843301.html
3.2 状态转移方程
依据题目要求:dp[i] = min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i -2]);
文章来源地址https://www.toymoban.com/news/detail-843301.html
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];
}
};
到了这里,关于【LeetCode】--- 动态规划 集训(一)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!