外贸网站做推广,wordpress用户中心UC,免费网站排名优化在线,wordpress id重置目录
1、记忆化搜索算法简介
1.1 什么是记忆化搜索
1.2 如何实现记忆化搜索
1.3 记忆化搜索与动态规划的区别
2、算法应用【leetcode】
2.1 题一#xff1a;斐波那契数
2.1.1 递归暴搜解法代码
2.1.2 记忆化搜索解法代码
2.1.3 动态规划解法代码
2.2 题二#xff1…目录
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 1n 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])再得len1(当加上前位置)就是当前位置的最长子序列。
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
