昆明做网站价格张文宏说上海可能是疫情爆发
文章目录
- 引言
- 一、不同路径
- 二、最长递增子序列
- 三、猜数字大小 ||
- 四、矩阵中的最长递增路径
- 总结
引言
记忆化搜索，本质上是dfs + 备忘录，优化相同问题的搜索，极大提高算法效率。同时，记忆化搜索和普通的动态规划实际上是一样的，记忆化搜索是递归的形式，而动态规划是递推（循环）的形式。
一、不同路径
细节：
- 设置备忘录的时候扩大一圈，方便处理边界情况：mem.resize(m + 1, vector(n + 1))
- 进入dfs递归，先看看备忘录是否存在该值，若存在则直接返回：if(mem[i][j] != 0) return mem[i][j]
- dfs(i, j)：表示到(i, j)位置的路径数量
- dfs(i, j) = dfs(i - 1, j) + dfs(i, j - 1)
- 初始化：
- if(i == 0 || j == 0) return 0
- if(i == 1 && j == 1) mem[i][j] = 1，return 1
- 每次递归结束后，将结果存储在备忘录中：mem[i][j] = dfs(i, j - 1) + dfs(i - 1, j)
记忆化搜索版本
class Solution
{vector<vector<int>> mem;
public:int dfs(int i, int j){if(mem[i][j] != 0) return mem[i][j];if(i == 0 || j == 0) return 0;if(i == 1 && j == 1){mem[i][j] = 1;return 1;}mem[i][j] = dfs(i, j - 1) + dfs(i - 1, j);return mem[i][j];}int uniquePaths(int m, int n){mem.resize(m + 1, vector<int>(n + 1));return dfs(m, n);}
};
动态规划版本
class Solution
{
public:int uniquePaths(int m, int n){vector<vector<int>> dp(m + 1, vector<int>(n + 1));dp[1][1] = 1;for(int i=1; i<=m; ++i){for(int j=1; j<=n; ++j){if(i == 1 && j == 1) continue;dp[i][j] = dp[i - 1][j] + dp[i][j - 1];}}return dp[m][n];}
};
二、最长递增子序列
思路：
- 进入dfs递归，先看看备忘录是否存在该值，若存在则直接返回：if(mem[pos] != 0) return mem[pos]
- 递推关系式：（当前节点小于子节点时）当前节点的最大长度，是所有子节点中的最大长度 + 1
- dfs函数：返回以pos开头的最长递增子序列的长度
- 每次递归结束后，将结果存储在备忘录中：mem[pos] = len
记忆化搜索版本
class Solution
{vector<int> mem;int n;
public:int dfs(vector<int>& nums, int pos)//返回以pos开头的最长递增子序列的长度{if(mem[pos] != 0) return mem[pos];int len = 1;for(int i=pos+1; i<n; ++i){if(nums[pos] < nums[i]){len = max(len, dfs(nums, i) + 1);}}mem[pos] = len;return len;}int lengthOfLIS(vector<int>& nums){n = nums.size();mem.resize(n);int ret = 0;for(int i=0; i<n; ++i){ret = max(ret, dfs(nums, i));}return ret;}
};
动态规划版本
class Solution
{
public:int lengthOfLIS(vector<int>& nums){int n = nums.size();vector<int> dp(n, 1);int ret = 0;for(int i=n-1; i>=0; --i){for(int j=i+1; j<n; ++j){if(nums[i] < nums[j]){dp[i] = max(dp[i], dp[j] + 1);}}ret = max(ret, dp[i]);}return ret;}
};
注意：记忆化搜索改动态规划，与直接动态规划的填表顺序不一样。
三、猜数字大小 ||
思路：
- 进入dfs递归，先看看备忘录是否存在该值，若存在则直接返回：if(mem[begin][end] != 0) return mem[begin][end]
- dfs函数：返回给定区间中获胜的最小金额
- 将begin到end这个大区间，分为两个区间
- 取两个区间中的最大金额，加上节点本身的金额，更新结果，取所有结果的最小值返回
- 每次递归结束后，将结果存储在备忘录中：mem[begin][end] = ret
class Solution
{int mem[201][201];
public:int dfs(int begin, int end){if(begin >= end) return 0;if(mem[begin][end] != 0) return mem[begin][end];int ret = INT_MAX;for(int i=begin; i<=end; ++i){int x = dfs(begin, i - 1), y = dfs(i + 1, end);ret = min(ret, i + max(x, y));}mem[begin][end] = ret;return ret;}int getMoneyAmount(int n){return dfs(1, n);}
};
四、矩阵中的最长递增路径
思路：
- 进入dfs递归，先看看备忘录是否存在该值，若存在则直接返回：if(mem[i][j] != 0) return mem[i][j]
- dfs函数：返回从(i, j)位置开始的最长递增路径的长度
- 递推关系式：（当下一个搜索的位置大于当前位置时）当前最长路径长度，为所有下一位置的最长长度的最大值 + 1
- 每次递归结束后，将结果存储在备忘录中：mem[i][j] = ret
class Solution
{int dx[4] = {1, -1, 0, 0};int dy[4] = {0, 0, 1, -1};int mem[201][201];int m, n;
public:int dfs(vector<vector<int>>& mat, int i, int j){if(mem[i][j] != 0) return mem[i][j];int ret = 1;for(int k=0; k<4; ++k){int x = i + dx[k], y = j + dy[k];if(x >= 0 && y >= 0 && x < m && y < n&& mat[x][y] > mat[i][j]){ret = max(ret, dfs(mat, x, y) + 1);}}mem[i][j] = ret;return ret;}int longestIncreasingPath(vector<vector<int>>& mat){m = mat.size(), n = mat[0].size();int ret = 0;for(int i=0; i<m; ++i){for(int j=0; j<n; ++j){ret = max(ret, dfs(mat, i, j));}}return ret;}
};
总结
记忆化搜索，主要难在递推关系式的推导，以及边界情况的把控，因为其本质就是动态规划。
当然，并不是所有题都很方便将记忆化搜索和动态规划相互转换，有些题写成记忆化搜索比较简单，有些题写成动态规划比较简单，因题而异。
