目前流行的app网站开发模式,app定制开发,建设购物网站需要多少钱,商业空间设计理念目录 一、1137. 第 N 个泰波那契数1.1 题目解析1.2 状态转移方程1.3 解题代码 二、面试题 08.01. 三步问题2.1 题目解析2.2 状态转移方程2.3 解题代码 三、746. 使用最小花费爬楼梯3.1 题目解析3.2 状态转移方程3.3 解题代码 一、1137. 第 N 个泰波那契数
题目地址#xff1a… 目录 一、1137. 第 N 个泰波那契数1.1 题目解析1.2 状态转移方程1.3 解题代码 二、面试题 08.01. 三步问题2.1 题目解析2.2 状态转移方程2.3 解题代码 三、746. 使用最小花费爬楼梯3.1 题目解析3.2 状态转移方程3.3 解题代码 一、1137. 第 N 个泰波那契数
题目地址 1137. 第 N 个泰波那契数 泰波那契序列 Tn定义如下 T0 0, T1 1, T2 1, 且在 n 0的条件下 Tn3 Tn Tn1 Tn2 给你整数 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;vectorint 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 级台阶的方法数可以定义一个长度为 n1 的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;vectorint 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 题目解析
此题所求的是达到楼梯顶部的最低花费那么我们便可定义一个长度为 n1 的 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(vectorint cost) {//1. 创建dp表//2. 初始化//3. 填表//4. 返回结束int n cost.size();vectorint 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];}
};
