布吉网站的建设,是想建个网站 用本地做服务器,网页框架是什么,建设网站需要租赁主机吗第N个泰波那契数
链接: 第N个泰波那契数
1137 . 第 N 个泰波那契数
泰波那契序列 Tn 定义如下#xff1a; T0 0, T1 1, T2 1, 且在 n 0 的条件下 Tn3 Tn Tn1 Tn2 给你整数 n#xff0c;请返回第 n 个泰波那契数 Tn 的值。
示例 1#xff1a; 输入#xff1a…第N个泰波那契数
链接: 第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.状态表示
dp[i] 表示的是第 i 个泰波那契数的值。
2.状态转移方程
动态规划题我们需要学会依靠经验和题目解析去猜测他们的状态转移方程。 这一题题目已经告诉我们了。
dp[i] dp[i - 1] dp[i - 2] dp[i - 3]3. 初始化
从我们的递推公式可以看出 dp[i] 在 i 0 以及 i 1 的时候是没有办法进⾏推导的因为dp[i-2] 或 dp[i-1] 不是⼀个有效的数据。
因此我们需要在填表之前将0, 1, 2 位置的值初始化。题⽬中已经告诉我们 dp[0] 0, dp[1] dp[2] 1 。
4. 填表顺序 按照数组下标的顺序从左往右。
5. 返回值 应该返回 dp[n] 的值。
代码
在写代码时按照此顺序
创建dp初始化填表返回值 int tribonacci(int n) {vectorint dp(n1);if(n0) return 0;if(n1||n2) return 1;dp[0]0;dp[1]dp[2]1;for(int i3;in;i){dp[i]dp[i-1]dp[i-2]dp[i-3];}return dp[n];}三步问题
链接: 三步问题
面试题 08.01. 三步问题
三步问题。有个小孩正在上楼梯楼梯有n阶台阶小孩一次可以上1阶、2阶或3阶。实现一种方法计算小孩有多少种上楼梯的方式。结果可能很大你需要对结果模1000000007。
示例1: 输入n 3 输出4 说明: 有四种走法
示例2: 输入n 5 输出13
1.状态表示
dp[i] 表示的是以 i 阶楼梯为结尾小孩跳动到此处的方式数。
2.状态转移方程
以i位置状态的最近的⼀步来分情况讨论 如果 dp[i] 表⽰⼩孩上第 i 阶楼梯的所有⽅式那么它应该等于所有上⼀步的⽅式之和
从 i-1 处跳⼀级台阶 dp[i] dp[i - 1] 从 i-2 处跳两级台阶 dp[i] dp[i - 2] 从 i-3 处跳三级台阶 dp[i] dp[i - 3]
dp[i] dp[i - 1] dp[i - 2] dp[i - 3]3. 初始化
从我们的递推公式可以看出 dp[i] 在 i 0 以及 i 1 的时候是没有办法进⾏推导的因为dp[i-2] 或 dp[i-1] 不是⼀个有效的数据。
因此我们需要在填表之前将0, 1, 2 位置的值初始化。我们可知 dp[1] 1, dp[2] 2dp[3]4;
4. 填表顺序 按照数组下标的顺序从左往右。
5. 返回值 应该返回 dp[n] 的值。
代码
此题会存在数据溢出的问题需要取模处理 int waysToStep(int n) {//创建dp//初始化//填表//返回值if(n2) return n;vectorint dp(n1);dp[1]1;dp[2]2;dp[3]4;for(int i4;in1;i){//取模dp[i]((dp[i-1]dp[i-2])%1000000007dp[i-3])%1000000007;}return dp[n];}
