算法笔记——路径问题

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

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

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

1.状态表示

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

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

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

---

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

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

2.状态转移方程

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

设求的是第i位的数据：

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

3.初始化

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

4.填表顺序

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

5.返回值

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

---

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

6.优化

在实现完代码后，可以用滚动数组进行一次空间的优化，减少时间和空间的复杂度