珠宝网站模版,天津市建设工程定额网站,网站建设海之睿,小程序多用户商城系统1. 第 N 个泰波那契数#xff08;easy#xff09;
1. 题目链接#xff1a;1137. 第 N 个泰波那契数
2. 题目描述 3.题目分析
这题我们要求第n个泰波那契Tn的值#xff0c;很明显的使用动态规划算法。
4.动态规划算法流程
1. 状态表示#xff1a;
根据题目的要求及公…1. 第 N 个泰波那契数easy
1. 题目链接1137. 第 N 个泰波那契数
2. 题目描述 3.题目分析
这题我们要求第n个泰波那契Tn的值很明显的使用动态规划算法。
4.动态规划算法流程
1. 状态表示
根据题目的要求及公式直接定义出状态表示我们以第i个位置为结尾dp表第i个位置的值表示第i个泰波那契的值。
2. 状态转移方程
根据公式我们确定dp[i]的值或者状态通过状态表示方程表示是dp[i] dp[i - 1] dp[i - 2] dp[i - 3]
3. dp表初始化 从我们的递推公式可以看出 dp[i] 在i 0 以及 i 1 的时候是没有办法进行推导的因 为 dp[-2] 或 dp[-1] 不是一个有效的数据。因此我们需要在填表之前将 0, 1, 2 位置的值初始化。题目中已经告诉我们 dp[0] 0, dp[1] dp[2] 1 我们按照题目的值初始化
4. 填表顺序 要求dp[i]的值就要先确定dp[i - 1]、 dp[i - 2]、dp[i - 3]的值因此dp表的填表顺序就是从左往右
5. 返回值
题目要求第n个数的值我们就应该返回 dp[n] 的值。
5.算法代码
class Solution {
public:int tribonacci(int n) {vectorint dp(n 1);if(n 0) return 0;//对于n为0,1,2的特殊情况我们需要处理一下防止越界if(n 1 || n 2) return 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];}
};
6.滚动数组优化
我们发现在求解上述问题的过程中我们只需要知道该位置前三的位置的值相加就行因此开辟O(n)的空间消耗完全没有必要我们使用滚动数组来进行优化滚动数组只是一种形象的说法并不一定是数组 算法代码展示
class Solution {
public:int tribonacci(int n) {int a 0,b 1,c 1,d 0;if(n 0) return 0;if(n 1 || n 2) return 1;for(int i 3;i n;i){d a b c;a b;b c;c d;}return d;}
};
