中天建设集团山西分公司网站,wordpress 邮件文章,wordpress表单样式,朋友圈广告投放平台个人主页#xff1a;元清加油_【C】,【C语言】,【数据结构与算法】-CSDN博客
个人专栏
力扣递归算法题 http://t.csdnimg.cn/yUl2I
【C】
http://t.csdnimg.cn/6AbpV
数据结构与算法 http://t.csdnimg.cn/hKh2l 前言#xff1a;这个专栏主要讲述动…个人主页元清加油_【C】,【C语言】,【数据结构与算法】-CSDN博客
个人专栏
力扣递归算法题 http://t.csdnimg.cn/yUl2I
【C】
http://t.csdnimg.cn/6AbpV
数据结构与算法 http://t.csdnimg.cn/hKh2l 前言这个专栏主要讲述动态规划算法所以下面题目主要也是这些算法做的
我讲述题目会把讲解部分分为3个部分 1、题目解析
2、算法原理思路讲解
3、代码实现 第 N 个泰波那契数
题目链接第 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提示
0 n 37答案保证是一个 32 位整数即 answer 2^31 - 1。 解法
题目解析
T0 0, T1 1, T2 1, 且在 n 0 的条件下 Tn3 Tn Tn1 Tn2。给你整数 n请返回第 n 个泰波那契数 Tn 的值。 算法原理讲解
我们这题使用动态规划我们做这类题目可以分为以下五个步骤
状态显示状态转移方程初始化防止填表时不越界填表顺序返回值 1.状态表示 这道题可以【根据题⽬的要求】直接定义出状态表示 dp[i] 表示第 i 个泰波那契数的值。 2.状态转移方程 题⽬已经⾮常贴⼼的告诉我们了 dp[i] dp[i - 1] dp[i - 2] dp[i - 3] 3.初始化 从我们的递推公式可以看出 dp[i] 在 i 0 以及 i 1 的时候是没有办法进⾏推导的因为 dp[-2] 或 dp[-1] 不是⼀个有效的数据。 因此我们需要在填表之前将 0, 1, 2 位置的值初始化。题⽬中已经告诉我们 dp[0] 0, dp[1] dp[2] 1 。 4.填表顺序 毫⽆疑问是「从左往右」。 5.返回值 应该返回 dp[n] 的值。 代码实现 时间复杂度O(n)。 空间复杂度O(1)。 一、使用一维数组 class Solution {
public:int tribonacci(int n) {if (n 0 || n 1) return n;vectorint dp(n 1);dp[0] 0;dp[1] 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];}
}; 二、使用滚动数组优化 class Solution {
public:int tribonacci(int n) {if (n 0 || n 1) return n;int p 0, q 0, r 1, s 1;for (int i 3; i n; i) {p q;q r;r s;s p q r;}return s;}
}; 三、递归超时
class Solution {
public:int tribonacci(int n) {if (n 0 || n 1) return n;if (n 2)return 1;return tribonacci(n-1) tribonacci(n-2) tribonacci(n-3);}
};
