算法笔记——路径问题-Toy模板网

这篇具有很好参考价值的文章主要介绍了算法笔记——路径问题。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

在引入介绍如何写一个算法的时候，我们先引入一个题作为例子

算法笔记——路径问题,笔记

1137. 第 N 个泰波那契数 - 力扣（LeetCode）

作为刚开始学习算法的我们，看到这个题目的时候，应该想好以下的问题：

1.状态表示

我们要用什么来表示每个位置的数值，甚至是返回哪个元素的下标对应的值？

怎么来？——返回的元素是按照题目的什么规律来实现？并且要满足题目的要求？

最后要发现问题中可能出现的子问题，防止有重复，栈溢出等问题。

由题目我们知道每个位置的数是由该数的前三个数据的累加得到的，所以这需要一个数据的存储

————用一个数组存放——dp表——存放到目前位置的数值

了解了需要状态的表示形势后，我们需要将底层逻辑用一个方程表达出来，也就是程序要进行的操作。

设求的是第i位的数据：

dp[i]=dp[i-1]+dp[i-2]+dp[i-3];

接着需要初始化。路径类题目起初都会有一些数据是固定的，那么我们要初始化一些位置的数据。同时也要保证数据访问的时候不会越界。

路径问题，填写当前位置的数据的时候，先前的数据已经计算过了——因为是一个逐渐递增的过程，不能跳过许多数据然后直接读取所需要的位置的数据。

要满足题目的要求，返回题目需要的数据

完成以上的操作后，大致的代码就可以实现了

在实现完代码后，可以用滚动数组进行一次空间的优化，减少时间和空间的复杂度文章来源地址https://www.toymoban.com/news/detail-693886.html

到了这里，关于算法笔记——路径问题的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！