记忆化搜索专题——算法简介力扣实战应用
目录
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;//memory
public 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