齐大胜请于果做网站是第几集,润滑油网站怎样做效果更好,商品分销平台,动漫设计与游戏制作专业快乐的流畅#xff1a;个人主页 个人专栏#xff1a;《算法神殿》《数据结构世界》《进击的C》 远方有一堆篝火#xff0c;在为久候之人燃烧#xff01; 文章目录 引言一、不同路径二、最长递增子序列三、猜数字大小 ||四、矩阵中的最长递增路径总结 引言
记忆化搜索… 快乐的流畅个人主页 个人专栏《算法神殿》《数据结构世界》《进击的C》 远方有一堆篝火在为久候之人燃烧 文章目录 引言一、不同路径二、最长递增子序列三、猜数字大小 ||四、矩阵中的最长递增路径总结 引言
记忆化搜索本质上是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 0if(i 1 j 1) mem[i][j] 1return 1 每次递归结束后将结果存储在备忘录中mem[i][j] dfs(i, j - 1) dfs(i - 1, j)
记忆化搜索版本
class Solution
{vectorvectorint 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, vectorint(n 1));return dfs(m, n);}
};动态规划版本
class Solution
{
public:int uniquePaths(int m, int n){vectorvectorint dp(m 1, vectorint(n 1));dp[1][1] 1;for(int i1; im; i){for(int j1; jn; 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]递推关系式当前节点小于子节点时当前节点的最大长度是所有子节点中的最大长度 1dfs函数返回以pos开头的最长递增子序列的长度每次递归结束后将结果存储在备忘录中mem[pos] len
记忆化搜索版本
class Solution
{vectorint mem;int n;
public:int dfs(vectorint nums, int pos)//返回以pos开头的最长递增子序列的长度{if(mem[pos] ! 0) return mem[pos];int len 1;for(int ipos1; in; i){if(nums[pos] nums[i]){len max(len, dfs(nums, i) 1);}}mem[pos] len;return len;}int lengthOfLIS(vectorint nums){n nums.size();mem.resize(n);int ret 0;for(int i0; in; i){ret max(ret, dfs(nums, i));}return ret;}
};动态规划版本
class Solution
{
public:int lengthOfLIS(vectorint nums){int n nums.size();vectorint dp(n, 1);int ret 0;for(int in-1; i0; --i){for(int ji1; jn; 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 ibegin; iend; 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(vectorvectorint mat, int i, int j){if(mem[i][j] ! 0) return mem[i][j];int ret 1;for(int k0; k4; 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(vectorvectorint mat){m mat.size(), n mat[0].size();int ret 0;for(int i0; im; i){for(int j0; jn; j){ret max(ret, dfs(mat, i, j));}}return ret;}
};总结
记忆化搜索主要难在递推关系式的推导以及边界情况的把控因为其本质就是动态规划。
当然并不是所有题都很方便将记忆化搜索和动态规划相互转换有些题写成记忆化搜索比较简单有些题写成动态规划比较简单因题而异。 真诚点赞手有余香
