记忆化搜索

斐波那契数 （通常用 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 <= n <= 30

3. 解法（暴搜 -> 记忆化搜索 -> 动态规划）：

🌴算法思路：

暴搜：

递归含义：给 dfs ⼀个使命，给他⼀个数 n ，返回第 n 个斐波那契数的值；
函数体：斐波那契数的递推公式；
递归出口：当 n == 0 或者 n == 1 时，不用套公式。

记忆化搜索：

加上一个备忘录；
每次进入递归的时候，去备忘录里面看看；
每次返回的时候，将结果加入到备忘录里面。

动态规划：

递归含义 -> 状态表示；
函数体 -> 状态转移方程；
递归出口 -> 初始化。

🌴算法代码：

class Solution 
{
    int memo[31];
public:
    int fib(int n) 
    {
        // 初始化备忘录
        memset(memo, -1, sizeof(memo));

        return dfs(n);
    }

    int dfs(int n)
    {
        if (memo[n] != -1)
        {
            return memo[n];// 直接去备忘录里边拿值
        }

        if (n == 0 || n == 1)
        {
            memo[n] = n;// 记录到备忘录里边
            return n;
        }

        memo[n] = dfs(n - 1) + dfs(n - 2);// 记录到备忘录里边
        return memo[n];
    }
};

二、不同路径

1. 题目链接：62. 不同路径

2. 题目描述：

一个机器人位于一个 m x n 网格的左上角（起始点在下图中标记为 “Start” ）。

机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。

问总共有多少条不同的路径？

示例 1：
输入：m = 3, n = 7
输出：28
示例 2：
输入：m = 3, n = 2
输出：3
解释：
从左上角开始，总共有 3 条路径可以到达右下角。
1. 向右 -> 向下 -> 向下
2. 向下 -> 向下 -> 向右
3. 向下 -> 向右 -> 向下
示例 3：
输入：m = 7, n = 3
输出：28
示例 4：
输入：m = 3, n = 3
输出：6
提示：

1 <= m, n <= 100
题目数据保证答案小于等于 2 * 109

3. 解法（暴搜 -> 记忆化搜索 -> 动态规划）：

🌴算法思路：

暴搜：

递归含义：给 dfs ⼀个使命，给他⼀个下标，返回从 [0, 0] 位置走到 [i, j] 位置一共有多少种方法；
函数体：只要知道到达上面位置的方法数以及到达左边位置的方法数，然后累加起来即可；
递归出口：当下标越界的时候返回 0 ；当位于起点的时候，返回 1 。

记忆化搜索：

加上一个备忘录；
每次进入递归的时候，去备忘录里面看看；
每次返回的时候，将结果加入到备忘录里面。

动态规划：

递归含义 -> 状态表示；
函数体 -> 状态转移方程；
递归出口 -> 初始化。

🌴算法代码：

class Solution 
{
public:
    int uniquePaths(int m, int n) 
    {
        vector<vector<int>> memo(m + 1, vector<int>(n + 1));// 备忘录
        return dfs(m, n, memo);
    }

    int dfs(int i, int j, vector<vector<int>>& memo)
    {
        if(memo[i][j] != 0)
        {
            return memo[i][j];
        }

        if(i ==0 || j ==0) return 0;
        if(i ==1 && j ==1)
        {
            memo[i][j] = 1;
            return memo[i][j];
        }

        memo[i][j] = dfs(i - 1, j, memo) + dfs(i, j - 1, memo);
        return memo[i][j];
    }
};

三、最长递增子序列

1. 题目链接：300. 最长递增子序列

2. 题目描述：

给定一个 m x n 整数矩阵 matrix ，找出其中 最长递增路径 的长度。

对于每个单元格，你可以往上，下，左，右四个方向移动。你不能在 对角线 方向上移动或移动到 边界外（即不允许环绕）。

示例 1：
输入：matrix = [[9,9,4],[6,6,8],[2,1,1]]
输出：4 
解释：最长递增路径为 [1, 2, 6, 9]。
示例 2：
输入：matrix = [[3,4,5],[3,2,6],[2,2,1]]
输出：4 
解释：最长递增路径是 [3, 4, 5, 6]。注意不允许在对角线方向上移动。
示例 3：
输入：matrix = [[1]]
输出：1
提示：

m == matrix.length
n == matrix[i].length
1 <= m, n <= 200
0 <= matrix[i][j] <= 231 - 1

3. 解法：

🌴算法思路：

暴搜：

递归含义：给 dfs ⼀个使命，给他⼀个数 i ，返回以 i 位置为起点的最长递增子序列的长度；
函数体：遍历 i 后面的所有位置，看看谁能加到 i 这个元素的后面。统计所有情况下的最大值。
递归出口：因为我们是判断之后再进入递归的，因此没有出口~

记忆化搜索：

加上⼀个备忘录；
每次进入递归的时候，去备忘录里面看看；
每次返回的时候，将结果加入到备忘录里面。

动态规划：

递归含义 -> 状态表示；
函数体 -> 状态转移方程；
递归出口 -> 初始化。

🌴算法代码：

class Solution
{
    int m, n;
    int dx[4] = {0, 0, 1, -1};
    int dy[4] = {1, -1, 0, 0};
    int memo[201][201];
public:
    int longestIncreasingPath(vector<vector<int>>& matrix) 
    {
        int ret = 0;
        m = matrix.size(), n = matrix[0].size();
        for (int i = 0; i < m; i++)
            for (int j = 0; j < n; j++)
            {
                ret = max(ret, dfs(matrix, i, j));
            }

        return ret;
    }

    int dfs(vector<vector<int>>& matrix, int i, int j)
    {
        if (memo[i][j] != 0) return memo[i][j];

        int ret = 1;
        for (int k = 0; k < 4; k++)
        {
            int x = i + dx[k], y = j + dy[k];
            if (x >= 0 && x < m && y >= 0 && y < n && matrix[x][y] > matrix[i][j])
            {
                ret = max(ret, dfs(matrix, x, y) + 1);
            }
        }
        memo[i][j] = ret;
        return ret;
    }
};

四、猜数字大小 II

1. 题目链接：375. 猜数字大小 II

2. 题目描述：

我们正在玩一个猜数游戏，游戏规则如下：

我从 1 到 n 之间选择一个数字。
你来猜我选了哪个数字。
如果你猜到正确的数字，就会 赢得游戏 。
如果你猜错了，那么我会告诉你，我选的数字比你的 更大或者更小 ，并且你需要继续猜数。
每当你猜了数字 x 并且猜错了的时候，你需要支付金额为 x 的现金。如果你花光了钱，就会 输掉游戏 。

给你一个特定的数字 n ，返回能够 确保你获胜 的最小现金数，不管我选择那个数字 。

示例 1：

输入：n = 10
输出：16
解释：制胜策略如下：
- 数字范围是 [1,10] 。你先猜测数字为 7 。
    - 如果这是我选中的数字，你的总费用为 $0 。否则，你需要支付 $7 。
    - 如果我的数字更大，则下一步需要猜测的数字范围是 [8,10] 。你可以猜测数字为 9 。
        - 如果这是我选中的数字，你的总费用为 $7 。否则，你需要支付 $9 。
        - 如果我的数字更大，那么这个数字一定是 10 。你猜测数字为 10 并赢得游戏，总费用为 $7 + $9 = $16 。
        - 如果我的数字更小，那么这个数字一定是 8 。你猜测数字为 8 并赢得游戏，总费用为 $7 + $9 = $16 。
    - 如果我的数字更小，则下一步需要猜测的数字范围是 [1,6] 。你可以猜测数字为 3 。
        - 如果这是我选中的数字，你的总费用为 $7 。否则，你需要支付 $3 。
        - 如果我的数字更大，则下一步需要猜测的数字范围是 [4,6] 。你可以猜测数字为 5 。
            - 如果这是我选中的数字，你的总费用为 $7 + $3 = $10 。否则，你需要支付 $5 。
            - 如果我的数字更大，那么这个数字一定是 6 。你猜测数字为 6 并赢得游戏，总费用为 $7 + $3 + $5 = $15 。
            - 如果我的数字更小，那么这个数字一定是 4 。你猜测数字为 4 并赢得游戏，总费用为 $7 + $3 + $5 = $15 。
        - 如果我的数字更小，则下一步需要猜测的数字范围是 [1,2] 。你可以猜测数字为 1 。
            - 如果这是我选中的数字，你的总费用为 $7 + $3 = $10 。否则，你需要支付 $1 。
            - 如果我的数字更大，那么这个数字一定是 2 。你猜测数字为 2 并赢得游戏，总费用为 $7 + $3 + $1 = $11 。
在最糟糕的情况下，你需要支付 $16 。因此，你只需要 $16 就可以确保自己赢得游戏。

示例 2：

输入：n = 1
输出：0
解释：只有一个可能的数字，所以你可以直接猜 1 并赢得游戏，无需支付任何费用。

示例 3：

输入：n = 2
输出：1
解释：有两个可能的数字 1 和 2 。
- 你可以先猜 1 。
    - 如果这是我选中的数字，你的总费用为 $0 。否则，你需要支付 $1 。
    - 如果我的数字更大，那么这个数字一定是 2 。你猜测数字为 2 并赢得游戏，总费用为 $1 。
最糟糕的情况下，你需要支付 $1 。

提示：

1 <= n <= 200

3. 解法：

🌴算法思路：

暴搜：

递归含义：给 dfs ⼀个使命，给他⼀个区间 [left, right] ，返回在这个区间上能完胜的最小费用；
函数体：选择 [left, right] 区间上的任意⼀个数作为头结点，然后递归分析左右子树。求出所有情况下的最小值；
递归出口：当 left >= right 的时候，直接返回 0 。

记忆化搜索：

加上一个备忘录；
每次进入递归的时候，去备忘录里面看看；
每次返回的时候，将结果加入到备忘录里面。

🌴算法代码：

class Solution 
{
    int memo[201][201];
public:
    int getMoneyAmount(int n) 
    {
        return dfs(1, n);
    }

    int dfs(int left, int right)
    {
        if (left >= right) return 0;
        if (memo[left][right] != 0) return memo[left][right];

        int ret = INT_MAX;
        for (int head = left; head < right; head++)
        {
            int x = dfs(left, head - 1);
            int y = dfs(head + 1, right);
            ret = min(ret, head + max(x, y));
        }
        memo[left][right] = ret;
        return ret;
    }
};

五、矩阵中的最长递增路径

1. 题目链接：329. 矩阵中的最长递增路径

2. 题目描述：

给定一个 m x n 整数矩阵 matrix ，找出其中 最长递增路径 的长度。

对于每个单元格，你可以往上，下，左，右四个方向移动。你不能在 对角线 方向上移动或移动到 边界外（即不允许环绕）。

示例 1：
输入：matrix = [[9,9,4],[6,6,8],[2,1,1]]
输出：4 
解释：最长递增路径为 [1, 2, 6, 9]。
示例 2：
输入：matrix = [[3,4,5],[3,2,6],[2,2,1]]
输出：4 
解释：最长递增路径是 [3, 4, 5, 6]。注意不允许在对角线方向上移动。
示例 3：
输入：matrix = [[1]]
输出：1
提示：

m == matrix.length
n == matrix[i].length
1 <= m, n <= 200
0 <= matrix[i][j] <= 2^31 - 1

3. 解法：

🌴算法思路：

暴搜：

递归含义：给 dfs ⼀个使命，给他⼀个下标 [i, j] ，返回从这个位置开始的最长递增路径的长度；
函数体：上下左右四个方向瞅⼀瞅，哪里能过去就过去，统计四个方向上的最大长度；
递归出口：因为我们是先判断再进入递归，因此没有出口~

记忆化搜索：

加上一个备忘录；
每次进入递归的时候，去备忘录里面看看；
每次返回的时候，将结果加入到备忘录里面。

🌴算法代码：

class Solution
{
    int m, n;
    int dx[4] = {0, 0, 1, -1};
    int dy[4] = {1, -1, 0, 0};
    int memo[201][201];
public:
    int longestIncreasingPath(vector<vector<int>>& matrix) 
    {
        int ret = 0;
        m = matrix.size(), n = matrix[0].size();
        for (int i = 0; i < m; i++)
            for (int j = 0; j < n; j++)
            {
                ret = max(ret, dfs(matrix, i, j));
            }

        return ret;
    }

    int dfs(vector<vector<int>>& matrix, int i, int j)
    {
        if (memo[i][j] != 0) return memo[i][j];

        int ret = 1;
        for (int k = 0; k < 4; k++)
        {
            int x = i + dx[k], y = j + dy[k];
            if (x >= 0 && x < m && y >= 0 && y < n && matrix[x][y] > matrix[i][j])
            {
                ret = max(ret, dfs(matrix, x, y) + 1);
            }
        }
        memo[i][j] = ret;
        return ret;
    }
};

原文地址：https://blog.csdn.net/weixin_65931202/article/details/142336658

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！

上一篇：vim的配置文件
下一篇：VirtualBox 网络设置

【学习日记】notebook添加JAVA支持
作者是个大学生这个专栏主要收集课时常用的软件以及女朋友上课用的软件的教程。需提前配置好java环境本篇仅对添加支持进行说明。新开了gitcode 用于上传安装包。解压进入解压后目录复制文件地
阅读更多2024-11-15
Docker与Podman全面比较
Docker和Podman作为两大容器引擎，各自拥有独特的特点和优势。本文将从溯源、特点、技术优势、应用实例和技术前景等方面对Docker和Podman进行全面比较。
阅读更多2024-11-15
算法学习blog：day2 继续记日记
4. 明日计划：至少五道题，并且要学会并实现今天的三道题，看这五道题的思路解法，下一天进行实现优化。除此之外pdf粗略看到了20页，明天继续看，后面才是重点。1.做了三道PAT 76，77，78，差一
阅读更多2024-11-15
基于Python的网上银行综合管理系统
【2025最新】基于python+django+vue+MySQL的网上银行综合管理系统，前后端分离。
阅读更多2024-11-15
自定义注解+拦截器+jwtFilter实现权限控制
GetterSUPER_ADMIN(1, "超级管理员"),SYSTEM_ADMIN(2, "系统管理员"),DOMESTIC_CONSUMER(3, &quo
阅读更多2024-11-15
前端面试题整理-vue指令开发
在 bind 钩子中，我为绑定的元素添加了一个点击事件监听器，当元素被点击时，执行复制操作。我当时在开发点击复制文本的功能，我有很多个元素都想有这个功能，但是我又不想每个元素都绑定一个 onClick
阅读更多2024-11-15
在使用ipc通信时，在渲染进程的Vue + TypeScript 开发过程，给window对象添加属性并赋值时，发生报错解决方法
在使用ipc通信时，在渲染进程的Vue + TypeScript 开发过程，给window对象添加属性并赋值时，发生报错解决方法
阅读更多2024-11-15
GESP4级考试语法知识（贪心算法（四））
GESP4级考试语法知识（贪心算法（四））
阅读更多2024-11-15
20241114在飞凌的OK3588-C的核心板上跑Linux R4时通过iperf3测试以太网卡的实际网速
创建一个eth0配置文件，配置文件的路径为：/etc/network/interfaces.d/eth0,设置动态ip的配置文件。虽然飞凌的OK3588-C的核心板使用的是千兆网卡RTL8211
阅读更多2024-11-15
【EmbeddedGUI】脏矩阵设计说明
脏矩阵设计说明
阅读更多2024-11-15

记忆化搜索

引言：

1. 什么是记忆化搜索？

2. 如何实现记忆化搜索？

一、斐波那契数

1. 题目链接：509. 斐波那契数

2. 题目描述：

3. 解法（暴搜 -> 记忆化搜索 -> 动态规划）：

🌴算法思路：

🌴算法代码：

二、不同路径

1. 题目链接：62. 不同路径

2. 题目描述：

3. 解法（暴搜 -> 记忆化搜索 -> 动态规划）：

🌴算法思路：

🌴算法代码：

三、最长递增子序列

1. 题目链接：300. 最长递增子序列

2. 题目描述：

3. 解法：

🌴算法思路：

🌴算法代码：

四、猜数字大小 II

1. 题目链接：375. 猜数字大小 II

2. 题目描述：

3. 解法：

🌴算法思路：

🌴算法代码：

五、矩阵中的最长递增路径

1. 题目链接：329. 矩阵中的最长递增路径

2. 题目描述：

3. 解法：

🌴算法思路：

🌴算法代码：

相关文章