目录
1、记忆化搜索算法简介
1.1 什么是记忆化搜索
1.2 如何实现记忆化搜索
1.3 记忆化搜索与动态规划的区别
2、算法应用【leetcode】
2.1 题一:斐波那契数
2.1.1 递归暴搜解法代码
2.1.2 记忆化搜索解法代码
2.1.3 动态规划解法代码
2.2 题二:不同路径
2.2.1 算法原理
2.2.2 记忆化搜索代码
2.2.3 动态规划代码
2.3 题三:最长递增子序列
2.3.1 算法原理
2.3.2 记忆化搜索代码
2.3.3 动态规划代码
2.4 题四:猜数字大小II
2.4.1 算法原理
2.4.2 算法代码
2.5 题五:矩阵中的最长递增路径【困难】
2.5.1 算法原理
2.5.2 算法代码
1、记忆化搜索算法简介
1.1 什么是记忆化搜索
记忆化搜索(Memoization)是一种优化搜索算法的技术,主要用于减少重复计算,提高算法效率。它通过存储已经计算过的结果来避免对同一问题的重复计算,特别适用于递归算法中存在大量完全重复的递归的情况。
简单来说,记忆化搜索就是带备忘录的递归。
举个例子,当我们使用普通的暴搜递归法求斐波那契数时,意味着每个节点都需要遍历一遍,时间复杂度为O(2^N),但是这其中出现大量完全重复的递归树,大量重复的递归导致时间效率严重降低。这时,我们就可以使用一个“备忘录”所出现过的数据存起来,递归时若遇见重复的问题时,直接从“备忘录”中取值即可,不必再次重复递归。这样一来,我们可将时间复杂优化为线性级别:O(N)。
我们以添加“备忘录”的形式,将数据记忆起来,减少大量重复的递归,这样的暴搜优化( O(2^N) --> O(N) )算法就称为记忆化搜索。
注意:
并非所有的递归暴搜都可改为记忆化搜索,只有在递归的过程中,出现了大量完全相同的问题时(并非相同子问题),才可以使用记忆化搜索进行优化。
1.2 如何实现记忆化搜索
- 添加备忘录 ---> <可变参数,返回值>
- 每次进入递归的时候,瞅一瞅备忘录里面是否已存在想要的结果
- 每次递归返回的时候,将结果放到备忘录中存起来
1.3 记忆化搜索与动态规划的区别
其实记忆化搜索与动态规划本质上都是一回事。
- 都属于暴力解法(暴搜)
- 都是对暴搜的优化:把计算过的值,存起来
但是不同的是:
- 记忆化搜索是以递归的形式进行的
- 动态规划是以递推(循环)的形式进行的
- 记忆化搜索是自顶向下(dfs(n) --> dfs(n-1) 、 dfs(n-2))
- 动态规划是自底向上(dp[1] 、 dp[2] --> dp[3] )
2、算法应用【leetcode】
2.1 题一:斐波那契数
. - 力扣(LeetCode)
相信对于斐波那契数的计算,大家都已了然于心,这里就不多废话了,只向大家展示三中不同解法:
- 递归暴搜解法:O(2^N)
- 记忆化搜索解法(暴搜优化):O(N)
- 动态规划解法(暴搜优化):O(N)
2.1.1 递归暴搜解法代码
class Solution {public int fib(int n) {return dfs(n);}public int dfs(int n) {if(n == 0 || n == 1) return n;return dfs(n - 1) + dfs(n - 2);}
}
2.1.2 记忆化搜索解法代码
class Solution {//记忆化搜索int[] memo;//memorypublic int fib(int n) {memo = new int[31];Arrays.fill(memo, -1);//初始化时,填入不可能出现的值return dfs(n);}public 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];}
}
2.1.3 动态规划解法代码
class Solution {//动态规划int[] dp;public int fib(int n) {dp = new int[31];dp[0] = 0; dp[1] = 1;for(int i = 2; i <= n; i++) {dp[i] = dp[i - 1] + dp[i - 2];}return dp[n];}
}
2.2 题二:不同路径
. - 力扣(LeetCode)
2.2.1 算法原理
经过分析,可以发现:到达(x,y)位置的路径数=到达(x,y-1)的路径数+到达(x-1,y)的路径数
设计递归函数体:dfs(m,n) = dfs(m,n-1)+dfs(m-1,n)
函数出口:
- if(m == 0 || n == 0) return 0;(从下标1开始为有效位置)
- if(m== 1&&n ==1) return 1;//特殊处理
经过验证,纯暴搜解法是会超时的,经分析,问题中出现了大量重复的问题,采取记忆化搜索算法和动态规划进行优化。
2.2.2 记忆化搜索代码
class Solution {//记忆化搜索int[][] memo;public int uniquePaths(int m, int n) {//从下标1,1开始memo = new int[m + 1][n + 1];return dfs(m, n);}public int dfs(int m, int n) {if(memo[m][n] != 0) return memo[m][n];if(m == 0 || n == 0) {return 0;}if(m == 1 && n == 1) {memo[m][n] = 1;return 1;}memo[m][n] = dfs(m, n - 1) + dfs(m - 1, n);return memo[m][n];}
}
2.2.3 动态规划代码
class Solution {public int uniquePaths(int m, int n) {//动态规划int[][] dp = new int[m + 1][n + 1];dp[1][1] = 1;for(int i = 1; i < m + 1; i++) {for(int j = 1;j < n + 1; j++) {if(i == 1 && j == 1) continue;dp[i][j] = dp[i][j - 1] + dp[i - 1][j];}}return dp[m][n];}
}
2.3 题三:最长递增子序列
2.3.1 算法原理
因为是最长递增子序列,所以只能从当前位置向后找。
- 函数头:dfs(pos);//pos位置处的最长子序列
- 从当前位置pos开始,选出后面位置中最长的子序列len(注意:要求nums[i] > nums[pos]),再得len+1(当加上前位置),就是当前位置的最长子序列。
2.3.2 记忆化搜索代码
class Solution {//记忆化搜索int n;public int lengthOfLIS(int[] nums) {int ret = 0;n = nums.length;int[] memo = new int[n];for(int i = 0; i < n; i++) {ret = Math.max(ret, dfs(nums, i, memo));}return ret;}public int dfs(int[] nums, int pos, int[] memo) {if(memo[pos] != 0) return memo[pos];int ret = 1;for(int i = pos + 1; i < n; i++) {if(nums[i] > nums[pos]) {ret = Math.max(ret, dfs(nums, i, memo) + 1);}}memo[pos] = ret;return ret;}
}
2.3.3 动态规划代码
class Solution {//动态规划int n;public int lengthOfLIS(int[] nums) {int ret = 0;n = nums.length;int[] dp = new int[n];Arrays.fill(dp, 1);for(int i = n - 1; i >= 0; i--) {for(int j = i + 1; j < n; j++) {if(nums[i] < nums[j]) {dp[i] = Math.max(dp[i], dp[j] + 1);}}ret = Math.max(dp[i], ret);}return ret;}
}
2.4 题四:猜数字大小II
. - 力扣(LeetCode)
2.4.1 算法原理
暴力枚举出所有可能出现的情况,选出花费最小的最佳策略。
- 每一种情况都需要选出左右子树中话费金额的最大值(保证能赢)
- 每种情况话费的金额为:max(左,右)+本身
- 选出所有情况中花费最小的最佳策略。
2.4.2 算法代码
class Solution {int[][] memo;public int getMoneyAmount(int n) {memo = new int[n + 1][n + 1];return dfs(1, n);}public int dfs(int s, int e) {int ret = Integer.MAX_VALUE;if(s >= e) {return 0;}if(memo[s][e] != 0) return memo[s][e];for(int i = s; i <= e; i++) {int left = dfs(s, i - 1);int right = dfs(i + 1, e);ret = Math.min(Math.max(left, right) + i, ret);}memo[s][e] = ret;return ret;}
}
2.5 题五:矩阵中的最长递增路径【困难】
. - 力扣(LeetCode)
2.5.1 算法原理
- 枚举所有节点,选出所有节点中最长的路径
- 函数设计:dfs(i,j) --> 返回(i,j)位置的最长路径
- 一个位置的最长路径是固定的 --> 备忘录int[][] memo
2.5.2 算法代码
class Solution {int m, n;int[] dx = {1, -1, 0, 0};int[] dy = {0, 0, 1, -1};int[][] matrix;int[][] memo;//备忘录public int longestIncreasingPath(int[][] matrix_) {matrix = matrix_;m = matrix.length; n = matrix[0].length;memo = new int[m + 1][n + 1];int ret = 0;for(int i = 0; i < m; i++) {for(int j = 0; j < n; j++) {ret = Math.max(ret, dfs(i, j));}}return ret;}public int dfs(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];int y = j + dy[k];if(x >= 0 && x < m && y >= 0 && y < n && matrix[x][y] > matrix[i][j]) {//求出当前位置的最长路径ret = Math.max(ret, dfs(x, y) + 1);}}memo[i][j] = ret;return ret;}
}
END