目录
引言:
1. 什么是记忆化搜索?
2. 如何实现记忆化搜索?
一、斐波那契数
1. 题目链接:509. 斐波那契数
2. 题目描述:
3. 解法(暴搜 -> 记忆化搜索 -> 动态规划):
🌴算法思路:
🌴算法代码:
二、不同路径
1. 题目链接:62. 不同路径
2. 题目描述:
3. 解法(暴搜 -> 记忆化搜索 -> 动态规划):
🌴算法思路:
🌴算法代码:
三、最长递增子序列
1. 题目链接:300. 最长递增子序列
2. 题目描述:
3. 解法:
🌴算法思路:
🌴算法代码:
四、猜数字大小 II
1. 题目链接:375. 猜数字大小 II
2. 题目描述:
3. 解法:
🌴算法思路:
🌴算法代码:
五、矩阵中的最长递增路径
1. 题目链接:329. 矩阵中的最长递增路径
2. 题目描述:
3. 解法:
🌴算法思路:
🌴算法代码:
引言:
1. 什么是记忆化搜索?
记忆化搜索(Memoization Search)是一种通过存储已经遍历过的状态信息,从而避免对同一状态重复遍历的搜索算法。它是动态规划的一种实现方式,特别适用于那些具有重叠子问题和最优子结构特性的问题。
在记忆化搜索中,当算法需要计算某个子问题的结果时,它首先检查是否已经计算过该问题。如果已经计算过,则直接返回已经存储的结果;否则,计算该问题,并将结果存储下来以备将来使用。这种方法可以显著减少重复计算,提高算法的效率。
2. 如何实现记忆化搜索?
实现记忆化搜索的基本步骤通常包括:
- 确定问题的动态规划状态和状态转移方程。
- 创建一个缓存结构(如数组或哈希表),用于存储子问题的解。
- 定义一个递归函数,用于计算问题的解。在递归过程中,首先检查缓存中是否已经有了当前子问题的解,如果有,则直接返回;如果没有,则计算该子问题,并将结果存储到缓存中。
- 调用递归函数并返回最终结果。
记忆化搜索与递推(自底向上的动态规划)的主要区别在于,记忆化搜索是自顶向下的解决问题方法,而递推是自底向上的方法。记忆化搜索适合那些状态转移方程复杂或递归深度不会太深的问题,而递推适合那些状态转移方程简单且递归深度可能过大的问题。
一、斐波那契数
1. 题目链接:509. 斐波那契数
2. 题目描述:
斐波那契数 (通常用
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;}
};