南京优质网站建设方案,制作彩票网站需要多少钱,云南专业网站制作公司,临沂森佳木业有限公司在引入介绍如何写一个算法的时候#xff0c;我们先引入一个题作为例子 1137. 第 N 个泰波那契数 - 力扣#xff08;LeetCode#xff09;
作为刚开始学习算法的我们#xff0c;看到这个题目的时候#xff0c;应该想好以下的问题#xff1a;
1.状态表示
我们要用什么来表…在引入介绍如何写一个算法的时候我们先引入一个题作为例子 1137. 第 N 个泰波那契数 - 力扣LeetCode
作为刚开始学习算法的我们看到这个题目的时候应该想好以下的问题
1.状态表示
我们要用什么来表示每个位置的数值甚至是返回哪个元素的下标对应的值
怎么来——返回的元素是按照题目的什么规律来实现并且要满足题目的要求
最后要发现问题中可能出现的子问题防止有重复栈溢出等问题。 由题目我们知道每个位置的数是由该数的前三个数据的累加得到的所以这需要一个数据的存储
————用一个数组存放——dp表——存放到目前位置的数值
2.状态转移方程
了解了需要状态的表示形势后我们需要将底层逻辑用一个方程表达出来也就是程序要进行的操作。
设求的是第i位的数据
dp[i]dp[i-1]dp[i-2]dp[i-3];
3.初始化
接着需要初始化。路径类题目起初都会有一些数据是固定的那么我们要初始化一些位置的数据。同时也要保证数据访问的时候不会越界。
4.填表顺序
路径问题填写当前位置的数据的时候先前的数据已经计算过了——因为是一个逐渐递增的过程不能跳过许多数据然后直接读取所需要的位置的数据。
5.返回值
要满足题目的要求返回题目需要的数据 完成以上的操作后大致的代码就可以实现了
6.优化
在实现完代码后可以用滚动数组进行一次空间的优化减少时间和空间的复杂度
