3d 网站设计,重庆刮刮卡制作,网站描述wordpress,公司部门部长是什么级别1.第 N 个泰波那契数
题目连接#xff1a;1137. 第 N 个泰波那契数 泰波那契序列 Tn 定义如下#xff1a; T0 0, T1 1, T2 1, 且在 n 0 的条件下 Tn3 Tn Tn1 Tn2给你整数 n#xff0c;请返回第 n 个泰波那契数 Tn 的值。
2.什么是动态规划
在解决这道问题之前…1.第 N 个泰波那契数
题目连接1137. 第 N 个泰波那契数 泰波那契序列 Tn 定义如下 T0 0, T1 1, T2 1, 且在 n 0 的条件下 Tn3 Tn Tn1 Tn2给你整数 n请返回第 n 个泰波那契数 Tn 的值。
2.什么是动态规划
在解决这道问题之前先来了解一下什么是动态规划。动态规划Dynamic Programming简称 DP是一种求解多阶段决策过程最优化问题的方法。简单的理解把原问题分解为相对简单的子问题先求解子问题再由子问题的解而得到原问题的解。 它的核心思想是把「原问题」分解为「若干个重叠的子问题」将子问题计算出来的结果存放到一张dp表中通过dp表中过往计算的结果来减少计算并计算出原问题。 它的解题步骤大致分为五个过程状态表⽰、状态转移⽅程、初始化、填表顺序、返回值
3.解决问题
(1)、状态表示 我们需要将子问题存放到一张dp表中而dp[i]就表示状态。对应这里的状态即为dp[i] 第 i 个泰波那契数的值。 (2)、状态转移⽅程 这道题就已经将状态转移方程给出我们稍微变形dp[i] dp[i - 1] dp[i - 2] dp[i - 3] (3)、初始化 由于dp[0]dp[1]dp[2]的数值题目以给出直接将值填入dp表中完成初始化。初始化时需要注意确保dp表下标不要越界。 (4)、初始化顺序 这里根据题目要求根据状态转移方程将dp填充。 (5)、返回值 返回dp[n]即为返回结果。
4.参考代码
C版本
class Solution
{
public:int tribonacci(int n) {vectorint dp(n 3,0);dp[1] dp[2] 1; for(int i 3;i n;i){dp[i] dp[i-3] dp[i - 2] dp[i -1];}return dp[n];}
};Python3版本
class Solution:def tribonacci(self, n: int) - int:list [0, 1, 1]for i in range(3, n 1):next_value list[i - 3] list[i - 2] list[i - 1]list.append(next_value)return list[n]5.空间优化
在上面的代码当中空间的复杂度为O(N)。关于这道题我们求出dp[n]的值只需要求n前三个状态。所以我们就可以使用滚动数组的方案来优化空间。如果求dp[n]只需要n前的若干个状态那么就可以使用滚动数组优化。 优化代码C版本
class Solution {
public:int tribonacci(int n) {if(n 0) return 0;if(n 1 || n 2) return 1;int a 0,b 1,c 1,d0;for(int i 3; i n;i){d a b c;// 滚动数组注意赋值顺序从前往后赋值[a,b,c] 不能后往前赋值[c,b,a]a b;b c;c d;}return d;}
};
