序言
虽然算法很难，但不应该就放弃。这是一个学习笔记，希望你们喜欢~
先自己尝试写，大概十几分钟仍然写不出来
看思路，再尝试跟着思路写
仍然写不出来，再看视频
b站up视频推荐：爱学习的饲养员
leetcode其他文章：
数组篇：
链表篇：
从小白开始刷算法 ListNode 链表篇 leetcode.203
从小白开始刷算法 ListNode 链表篇 leetcode.206
队列篇
从小白开始刷算法 ListNode 链表篇 leetcode.933
栈篇
从小白开始刷算法 Stack 栈篇 leetcode.496
哈希篇
从小白开始刷算法 Hash 哈希篇 leetcode.217
从小白开始刷算法 Hash 哈希篇 leetcode.705
树篇
从小白开始刷算法 Tree 树篇 先序遍历 leetcode.144
从小白开始刷算法 Tree 树篇 中序遍历 leetcode.94
从小白开始刷算法 Tree 树篇 后序遍历 leetcode.94
堆篇
从小白开始刷算法 Heap 堆篇 最大堆排序 leetcode.215
小白开始刷算法 Heap 堆篇 最小堆排序 leetcode.692
双指针篇
二分法篇
滑动窗口篇
递归篇
分治法篇
回溯法篇
dfs篇
bfs篇
并查集篇
记忆化搜索篇
难度：简单
题目：
509. 斐波那契数
斐波那契数 （通常用 F(n) 表示）形成的序列称为 斐波那契数列 。该数列由 0 和 1 开始，后面的每一项数字都是前面两项数字的和。也就是：
F(0) = 0，F(1) = 1
F(n) = F(n - 1) + F(n - 2)，其中 n > 1
给定 n ，请计算 F(n) 。
示例 1：
输入：n = 2
输出：1
解释：F(2) = F(1) + F(0) = 1 + 0 = 1
示例 2：
输入：n = 3
输出：2
解释：F(3) = F(2) + F(1) = 1 + 1 = 2
示例 3：
输入：n = 4
输出：3
解释：F(4) = F(3) + F(2) = 2 + 1 = 3
题目来源：力扣（LeetCode）
记忆化搜索
也称为动态规划的一种优化技术，是在递归算法的基础上添加了缓存（或称为记忆化数组或备忘录），以避免重复计算子问题，提高算法的效率。
在使用记忆化搜索时，我们将计算过的结果存储在一个数组（通常称为memo或cache）中，以便在后续的计算中可以直接访问和复用这些结果。这样，当遇到相同的子问题时，我们只需查找缓存中是否已经计算过该子问题的结果，如果已经计算过，则直接返回结果，而无需重新计算。
记忆化搜索常用于解决具有重叠子问题特性的问题，其中同一个子问题会被多次计算。通过使用记忆化，我们可以避免重复计算，减少时间复杂度，提高算法的执行速度。
记忆化搜索的步骤通常包括：
- 创建一个用于存储计算结果的缓存（memo）。
- 在每次计算前，先检查缓存中是否已经存在计算结果。
- 如果缓存中已经存在计算结果，则直接返回结果。
- 如果缓存中不存在计算结果，则进行计算，并将结果存入缓存中。
- 在递归过程中，按照需要计算子问题，并利用缓存中的结果进行计算。
- 最终返回所需的结果。
记忆化搜索可以有效地减少重复计算，提高算法的效率，尤其在递归算法中应用广泛。它常用于解决一些经典的问题，如斐波那契数列、背包问题、图算法等。通过合理地设计缓存结构和递归逻辑，可以将指数级的时间复杂度降低为多项式级别，从而实现高效的算法解决方案。
递归+记忆化搜索 思路
能否写出：能写出。
时间：20分钟左右
思路：
思路与从小白开始刷算法 递归篇 leetcode.509一样
在fibMemoization方法中，首先判断如果n小于等于1，则直接返回n，与fib方法相同。
然后，检查memo数组中是否已经存在计算过的结果，即memo[n]是否不等于-1。如果不等于-1，说明已经计算过该值，直接返回该结果。
如果memo[n]等于-1，表示尚未计算过该值，需要进行计算。计算过程为将前两个斐波那契数的结果相加，即fibMemoization(n - 1, memo) + fibMemoization(n - 2, memo)。然后将计算结果存入memo[n]中。
最后，返回memo[n]作为结果。
通过使用记忆化搜索的思路，可以避免重复计算斐波那契数列中的子问题，从而大大提高计算效率。记忆化搜索的时间复杂度是线性的，即O(n)。
// 仅是我的思路代码，leetcode上大神更厉害 class Solution { public int fib(int n) { if (n <= 1) { return n; } //新建记忆化数组 int[] memo = new int[n + 1]; //初始化 数组 Arrays.fill(memo, -1); return fibMemoization(n,memo); } private int fibMemoization(int n, int[] memo) { if (n <= 1) { return n; } //判断 memo 数组中是否已经存在计算过的结果 if (memo[n] != -1) { return memo[n]; } //将结果存入memo[n]中 memo[n] = fibMemoization(n - 1, memo) + fibMemoization(n - 2, memo); return memo[n]; } }
时间复杂度：O(N)
- 对于每个n，我们只计算一次斐波那契数，然后将结果存储在memo数组中。之后的计算都是通过查找memo数组来获得结果，而不需要重复计算。
空间复杂度：O(N)
- 由memo数组所占用的空间决定。memo数组的大小是n+1，因此空间复杂度与输入规模n成正比。
