郑州网站设计与制作,快站如何做网站,学生处网站建设工作总结,网站seo推广优化教程文章目录 题目描述算法原理1.状态表示(最重要的#xff09;什么是状态表示#xff1f;状态表示怎么来的呢#xff1f;本题的状态表示 2.状态转移方程(最难的#xff09;本题的状态转移方程 3.初始化(后三步完成剩下百分之一的细节问题#xff09;本题的初始化 4.填表顺序本… 文章目录 题目描述算法原理1.状态表示(最重要的什么是状态表示状态表示怎么来的呢本题的状态表示 2.状态转移方程(最难的本题的状态转移方程 3.初始化(后三步完成剩下百分之一的细节问题本题的初始化 4.填表顺序本题的填表顺序 5.返回值本题返回值 代码实现空间优化 题目描述
题目链接1137.第N个泰波那契数
算法原理
如果我们采用动态规划的思想来解决这道问题的话我们的过程一般是分五步来解决的
1.状态表示(最重要的
什么是状态表示
首先我们要先确定一个状态表示。那第一次接触动态规划的同学可能就有些疑问了什么是状态表示呢通俗的来讲就是我们会先定义一个dp表这个dp表可能是一维数组或者二维数组简单举例一下 我们做动态规划的流程就是搞一个dp表然后把他填满其中一个值可能就是我们的答案状态表示指的就是dp表中的某个值它所代表的含义(感性理解)。如果我们去直接去百度动态规划的状态表示是什么的话会出现一堆概念性的专有名词要是没一两周根本搞不懂而且会很痛苦很容易放弃所以刚开始学的时候我们有一个感性的认知就可以了。
状态表示怎么来的呢
(PS很多教学视频上来就给一个状态表示而不说明状态表示怎么来的那后续的步骤则显得毫无意义
题目要求经验(一两百道题)题目要求分析问题的过程中发现重复子问题(表示动态规划的方式)
第三个看起来也有点抽象但问题不大前期跟紧我的节奏先理解前两步慢慢的等我们动态规划学的熟练了就会进而引出第三种了。当然也会有其它的但我这个系列只会涉及这三个。
本题的状态表示
dp[i]表示第i个泰波那契数的值
2.状态转移方程(最难的
dp[i]等于什么状态转移方程就是什么。所以我们要想尽一切办法来让之前的状态或者之后的状态来表示dp[i]。
本题的状态转移方程
题目非常贴心已经给出dp[i]dp[i-1]dp[i-2]dp[i-3]
3.初始化(后三步完成剩下百分之一的细节问题
根据状态转移方程来填表保证填表的时候不越界
本题的初始化
dp[0]0dp[1]1dp[2]1
4.填表顺序
为了填写状态的时候所需要的状态已经计算过了。
本题的填表顺序
从左向右
5.返回值
题目要求状态表示
本题返回值
dp[n]
代码实现
class Solution {
public:int tribonacci(int n) {//时间复杂度和空间复杂度都为O(N)//处理一些越界情况if(n 1)return n;else if(n 2)return 1;//1.状态表示vectorint dp(n 1);//2.初始化dp[0] 0,dp[1] 1,dp[2] 1;//3.填表顺序for(int i 3;i n;i){dp[i] dp[i - 3] dp[i - 2] dp[i - 1];}//返回值return dp[n];}
};空间优化 每次滚动则之前的数可以舍去。
class Solution {
public:int tribonacci(int n) {//滚动数组空间优化——空间复杂度从O(N)变为O(1)//处理一些边界情况if(n 1)return n;else if(n 2)return 1;//初始化int a 0,b 1,c 1,x 0;//填表顺序for(int i 3;i n;i){x a b c;a b;b c;c x;}//返回值return x;}
};
