【算法专题】记忆化搜索

记忆化搜索

• • 1. 斐波那契数(记忆化搜索)
  • 2. 不同路径Ⅱ(记忆化搜索)
  • 3. 最长递增子序列(记忆化搜索)
  • 4. 猜数字大小Ⅱ
  • 5. 矩阵中的最长递增路径

    什么是记忆化搜索呢？记忆化搜索其实就是带了"备忘录"的递归，给递归加上一个"备忘录"，递归每次返回的时候，将结果放到"备忘录"里面，在每次进入递归的时候，往"备忘录"里面看看，当前需要递归的数据时候在"备忘录"里存在，如果存在，那么就可以直接取此次的结果，不用进行这次的递归。

    下面我们看一道经典的递归题可以使用记忆化搜索优化：

    1. 斐波那契数(记忆化搜索)

    题目链接 -> Leetcode -509.斐波那契数(记忆化搜索)

    Leetcode -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

    提示：

    • 0 向下->向下
    • 向下->向下->向右
    • 向下->向右->向下

    示例 3：

    输入：m = 7, n = 3

    输出：28

    示例 4：

    输入：m = 3, n = 3

    输出：6

    提示：

    • 1