当前位置:   article > 正文

算法:DFS之记忆化搜索

算法:DFS之记忆化搜索

目录

记忆化搜索

题目一:不同路径

题目二:最长递增子序列

题目三:猜数字大小II

题目四:矩阵中的最长递增路径


记忆化搜索

说到记忆化搜索,首先就需要引入斐波那契数这道题,非常经典,可以很好地说明什么是记忆化搜索

斐波那契数列

首先是列举递归的做法:

  1. class Solution
  2. {
  3. public:
  4. int fib(int n)
  5. {
  6. return dfs(n);
  7. }
  8. int dfs(int n)
  9. {
  10. if(n == 0 || n == 1)
  11. return n;
  12. return dfs(n - 1) + dfs(n - 2);
  13. }
  14. };

这种做法非常简便,但是时间复杂度也非常高,近似于O(2^N)

而之所以慢,是因为有很多数都重复递归计算了,例如dfs(5)时,会计算dfs(4)和dfs(3),其中计算dfs(4)时,又会计算dfs(3)和dfs(2)
dfs(5)和dfs(4)都重复计算dfs(3)了,再往下看,重复计算的数更多,所以就会导致时间复杂度非常高

而如果想优化也非常简单,我们每计算出一个值,就将其放入“备忘录”中,如果后续又需要用到这个值,就不需要重复计算了,可以直接使用,所以引出记忆化搜索概念:

记忆化搜索

记忆化搜索其实就是带备忘录的递归

也就相当于递归过程中的剪枝操作了,相当于将一个指数级别的时间复杂度,变为了O(N)级别的,因为只需要计算出一次,剩下分支就可以直接使用,不会进入递归了                                        

所以记忆化搜索的代码实现的步骤就是:

①添加一个备忘录并初始化
②递归每次返回时,将结果放入备忘录中
③每次进入递归时,查看备忘录中是否已经有结果

记忆化搜索代码如下:

  1. class Solution
  2. {
  3. public:
  4. int memo[31];
  5. int fib(int n)
  6. {
  7. // 创建一个备忘录并初始化
  8. memset(memo, -1, sizeof(memo));
  9. return dfs(n);
  10. }
  11. int dfs(int n)
  12. {
  13. if(memo[n] != -1)
  14. {
  15. // 每次进入递归时,查看备忘录中是否已经有结果
  16. return memo[n];
  17. }
  18. if(n == 0 || n == 1)
  19. {
  20. memo[n] = n; // 递归每次返回时,将结果放入备忘录中
  21. return n;
  22. }
  23. // 递归每次返回时,将结果放入备忘录中
  24. memo[n] = dfs(n - 1) + dfs(n - 2);
  25. return memo[n];
  26. }
  27. };

题目一:不同路径

一个机器人位于一个 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. class Solution
  2. {
  3. public:
  4. int uniquePaths(int m, int n)
  5. {
  6. return dfs(m ,n);
  7. }
  8. int dfs(int i, int j)
  9. {
  10. // 两个边界条件
  11. if(i == 0 || j == 0) return 0;
  12. if(i == 1 && j == 1) return 1;
  13. return dfs(i - 1, j) + dfs(i, j - 1);
  14. }
  15. };

因为时间复杂度太高了,所以是会超时的

二、改为记忆化搜索

  1. class Solution
  2. {
  3. public:
  4. int uniquePaths(int m, int n)
  5. {
  6. // 添加一个备忘录并初始化
  7. vector<vector<int>> memo(m + 1, vector<int>(n + 1));
  8. return dfs(m ,n, memo);
  9. }
  10. int dfs(int i, int j, vector<vector<int>>& memo)
  11. {
  12. // 每次进入递归时,查看备忘录中是否已经有结果
  13. if(memo[i][j] != 0)
  14. {
  15. return memo[i][j];
  16. }
  17. if(i == 0 || j == 0) return 0;
  18. // 递归每次返回时,将结果放入备忘录中
  19. if(i == 1 && j == 1)
  20. {
  21. memo[i][j] = 1;
  22. return memo[i][j];
  23. }
  24. // 递归每次返回时,将结果放入备忘录中
  25. memo[i][j] = dfs(i - 1, j, memo) + dfs(i, j - 1, memo);
  26. return memo[i][j];
  27. }
  28. };

三、改为动态规划

  1. class Solution
  2. {
  3. public:
  4. int uniquePaths(int m, int n)
  5. {
  6. vector<vector<int>> dp(m + 1, vector<int>(n + 1));
  7. dp[1][1] = 1;
  8. for(int i = 1; i <= m; i++)
  9. for(int j = 1; j <= n; j++)
  10. {
  11. if(i == 1 && j == 1) continue;
  12. dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
  13. }
  14. return dp[m][n];
  15. // 添加一个备忘录并初始化
  16. // vector<vector<int>> memo(m + 1, vector<int>(n + 1));
  17. // return dfs(m ,n, memo);
  18. }
  19. };

题目二:最长递增子序列

给你一个整数数组 nums ,找到其中最长严格递增子序列的长度。

子序列 是由数组派生而来的序列,删除(或不删除)数组中的元素而不改变其余元素的顺序。例如,[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列

示例 1:

输入:nums = [10,9,2,5,3,7,101,18]
输出:4
解释:最长递增子序列是 [2,3,7,101],因此长度为 4 。

示例 2:

输入:nums = [0,1,0,3,2,3]
输出:4

示例 3:

输入:nums = [7,7,7,7,7,7,7]
输出:1

子序列也就是数组中不连续的序列,本题求的就是不连续的递增子序列的最大长度是多少

下面进行暴力搜索、记忆化搜索、改为动态规划三步

一、递归暴力搜索

暴力搜索就是在决策树中,首先确定子序列的起点是哪一个数,依次列举出来,第二层就是根据第一层列举出来的起点数字,从该数往后依次继续列举,直到最后一个数为止

  1. class Solution
  2. {
  3. public:
  4. int ret;
  5. int lengthOfLIS(vector<int>& nums)
  6. {
  7. for(int i = 0; i < nums.size(); i++)
  8. ret = max(ret, dfs(nums, i));
  9. return ret;
  10. }
  11. int dfs(vector<int>& nums, int pos)
  12. {
  13. // 寻找该数字后面的最长子序列,需要加上该数字,所以初始化为1
  14. int ret = 1;
  15. for(int i = pos + 1; i < nums.size(); i++)
  16. {
  17. // 符合条件再递归
  18. if(nums[i] > nums[pos])
  19. ret = max(ret, dfs(nums, i) + 1);
  20. }
  21. return ret;
  22. }
  23. };

本题的暴力搜索同样会超时


二、记忆化搜索

  1. class Solution
  2. {
  3. public:
  4. int ret;
  5. int lengthOfLIS(vector<int>& nums)
  6. {
  7. // 添加一个备忘录并初始化
  8. int n = nums.size();
  9. vector<int> memo(n);
  10. // 哪个位置为最长子序列的起点不确定,所以每个位置都寻找一次
  11. for(int i = 0; i < n; i++)
  12. ret = max(ret, dfs(nums, i, memo));
  13. return ret;
  14. }
  15. int dfs(vector<int>& nums, int pos, vector<int>& memo)
  16. {
  17. // 每次进入递归时,查看备忘录中是否已经有结果
  18. if(memo[pos] != 0) return memo[pos];
  19. // 寻找该数字后面的最长子序列,需要加上该数字,所以初始化为1
  20. int ret = 1;
  21. for(int i = pos + 1; i < nums.size(); i++)
  22. {
  23. // 符合条件再递归
  24. if(nums[i] > nums[pos])
  25. ret = max(ret, dfs(nums, i, memo) + 1);
  26. }
  27. // 递归每次返回时,将结果放入备忘录中
  28. memo[pos] = ret;
  29. return memo[pos];
  30. }
  31. };

加上备忘录后,就能运行通过,不会超时了


三、改为动态规划

因为本题也有相同的子问题,会重复计算,例如选择第一个数字作为子序列起点时,会递归到第二个数字,此时就会与初始选择第二个数字做起点重复计算

这里的动态规划版本与动态规划章节里的方式不同,因为此题的动态规划版本是依据记忆化搜索的版本做的改变

因为记忆化搜索中,想知道该位置为起点的最长子序列,需要知道该位置之后的最长子序列,所以是从后向前的

dfs与dp是对应的

  1. class Solution
  2. {
  3. public:
  4. int lengthOfLIS(vector<int>& nums)
  5. {
  6. int n = nums.size(), ret = 0;
  7. // 与记忆化搜索相同,初始化为1
  8. vector<int> dp(n, 1);
  9. // 从后向前
  10. for(int i = n - 1; i >= 0; i--)
  11. {
  12. for(int j = i + 1; j < n; j++)
  13. {
  14. if(nums[j] > nums[i])
  15. dp[i] = max(dp[i], dp[j] + 1);
  16. }
  17. ret = max(ret, dp[i]);
  18. }
  19. return ret;
  20. // 添加一个备忘录并初始化
  21. // int n = nums.size();
  22. // vector<int> memo(n);
  23. // 哪个位置为最长子序列的起点不确定,所以每个位置都寻找一次
  24. // for(int i = 0; i < n; i++)
  25. // ret = max(ret, dfs(nums, i, memo));
  26. // return ret;
  27. }
  28. };

题目三:猜数字大小II

我们正在玩一个猜数游戏,游戏规则如下:

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

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


猜数字我们都玩过,这道题与传统猜数字不同的是,如果猜错需要支付当前猜的数字的钱

题目要求我们计算出在某一种选择策略中,无论选择的是数字几,都能确保获胜所花的现金数能够获胜,求这些策略中需要的最小的现金数

所以第一步,先考虑暴力搜索怎么做

第一步确定需要选的值是多少,假设该数在 1 ~ 10 之间,此时如果选择 i 

那么可能  i 比所需要的数小,也可能比所需要的数大,所以决策树向左延伸就是 1 ~ i - 1
向右延伸就是 i + 1 ~ 10

由于需要的就是满足条件的最小值,所以在 i 下面扩展的 1 ~ i - 1 与 i + 1 ~ 10中,需要选择最小值向上返回,假设 1 ~ i - 1 区间返回 x,i + 1 ~ 10区间返回 y,那么最后的结果应该是
i + max(x, y),因为最终需要的结果是能够满足当前选择的任意情况,同时还需要加上当前数字的值

也就是上面这种图中,7就表示i,下一层的3和9就表示扩展的1~6和8~10之间选择的一种情况,3返回的是3 + 5 == 8,而9 返回的是 9,所以根节点7为了能够满足这两种情况,最终选择的是9,结果就是 9 + 7 == 16

一、暴力搜索的代码如下:

  1. class Solution
  2. {
  3. public:
  4. int getMoneyAmount(int n)
  5. {
  6. return dfs(1, n);
  7. }
  8. int dfs(int left, int right)
  9. {
  10. if(left >= right) return 0;
  11. int ret = INT_MAX;
  12. for(int head = left; head <= right; head++)
  13. {
  14. // x和y表示head下面左右分支返回上来的值
  15. int x = dfs(left, head - 1);
  16. int y = dfs(head + 1, right);
  17. ret = min(ret, max(x, y) + head);
  18. }
  19. return ret;
  20. }
  21. };

这种解法肯定是超时的,所以看下面的记忆化搜索代码


 二、改为记忆化搜索

很简单,只需创建备忘录,再在返回时存入与进入递归时查看是否有值即可

只需要加上两行代码,就可以剪枝减掉非常多种情况,因此相比于暴力搜索的代码就不会超时了

代码如下:

  1. class Solution
  2. {
  3. public:
  4. int memo[201][201];
  5. int getMoneyAmount(int n)
  6. {
  7. return dfs(1, n);
  8. }
  9. int dfs(int left, int right)
  10. {
  11. if(left >= right) return 0;
  12. if(memo[left][right] != 0) return memo[left][right];
  13. int ret = INT_MAX;
  14. for(int head = left; head <= right; head++)
  15. {
  16. // x和y表示head下面左右分支返回上来的值
  17. int x = dfs(left, head - 1);
  18. int y = dfs(head + 1, right);
  19. ret = min(ret, max(x, y) + head);
  20. }
  21. memo[left][right] = ret;
  22. return memo[left][right];
  23. }
  24. };

题目四:矩阵中的最长递增路径

给定一个 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

本题同样需要先写出暴力解法,就是将每个位置都遍历一遍,再返回计算出的最大的值接口

肯定也会超时的,因为在暴力解法中,每一个位置可能都会计算多次

暴力搜索代码如下:

  1. class Solution {
  2. public:
  3. int dx[4] = {0,0,-1,1};
  4. int dy[4] = {-1,1,0,0};
  5. int ret, m, n;
  6. int longestIncreasingPath(vector<vector<int>>& matrix) {
  7. m = matrix.size(), n = matrix[0].size();
  8. ret = 0;
  9. for(int i = 0; i < m; i++)
  10. {
  11. for(int j = 0; j < n; j++)
  12. {
  13. ret = max(ret, dfs(matrix, i, j));
  14. }
  15. }
  16. return ret;
  17. }
  18. int dfs(vector<vector<int>>& matrix, int i, int j)
  19. {
  20. int ret = 1;
  21. for(int k = 0; k < 4; k++)
  22. {
  23. int x = i + dx[k];
  24. int y = j + dy[k];
  25. if(x >= 0 && x < m && y >= 0 && y < n && matrix[x][y] > matrix[i][j])
  26. {
  27. ret = max(ret, dfs(matrix, x, y) + 1);
  28. }
  29. }
  30. return ret;
  31. }
  32. };

更新为记忆化搜索的代码,此时就不会超时了,成功解决问题:

  1. class Solution {
  2. public:
  3. int dx[4] = {0,0,-1,1};
  4. int dy[4] = {-1,1,0,0};
  5. int ret, m, n;
  6. int memo[201][201];
  7. int longestIncreasingPath(vector<vector<int>>& matrix) {
  8. m = matrix.size(), n = matrix[0].size();
  9. ret = 0;
  10. for(int i = 0; i < m; i++)
  11. {
  12. for(int j = 0; j < n; j++)
  13. {
  14. ret = max(ret, dfs(matrix, i, j));
  15. }
  16. }
  17. return ret;
  18. }
  19. int dfs(vector<vector<int>>& matrix, int i, int j)
  20. {
  21. if(memo[i][j] != 0) return memo[i][j];
  22. int ret = 1;
  23. for(int k = 0; k < 4; k++)
  24. {
  25. int x = i + dx[k];
  26. int y = j + dy[k];
  27. if(x >= 0 && x < m && y >= 0 && y < n && matrix[x][y] > matrix[i][j])
  28. {
  29. ret = max(ret, dfs(matrix, x, y) + 1);
  30. }
  31. }
  32. memo[i][j] = ret;
  33. return memo[i][j];
  34. }
  35. };

记忆化搜索相关题目到此结束

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/正经夜光杯/article/detail/1002140
推荐阅读
相关标签
  

闽ICP备14008679号