记忆化搜索专题——算法简介力扣实战应用

目录

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. 添加备忘录 ---> <可变参数,返回值>
  2. 每次进入递归的时候,瞅一瞅备忘录里面是否已存在想要的结果
  3. 每次递归返回的时候,将结果放到备忘录中存起来

1.3 记忆化搜索与动态规划的区别

其实记忆化搜索与动态规划本质上都是一回事。

  1. 都属于暴力解法(暴搜)
  2. 都是对暴搜的优化:把计算过的值,存起来

但是不同的是:

  1. 记忆化搜索是以递归的形式进行的
  2. 动态规划是以递推(循环)的形式进行的
  3. 记忆化搜索是自顶向下(dfs(n) --> dfs(n-1) 、 dfs(n-2))
  4. 动态规划是自底向上(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)

函数出口:

  1. if(m == 0 || n == 0) return 0;(从下标1开始为有效位置)
  2. 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

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/428145.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

vue-使用refs取值,打印出来是个数组??

背景&#xff1a; 经常使用$refs去获取组件实例&#xff0c;一般都是拿到实例对象&#xff0c;这次去取值的时候发现&#xff0c;拿到的竟然是个数组。 原因&#xff1a; 这是vue的特性,自动把v-for里面的ref展开成数组的形式&#xff0c;哪怕你的ref名字是唯一的&#xff01…

后台数据管理系统 - 项目架构设计-Vue3+axios+Element-plus(0916)

接口文档: https://apifox.com/apidoc/shared-26c67aee-0233-4d23-aab7-08448fdf95ff/api-93850835 接口根路径&#xff1a; http://big-event-vue-api-t.itheima.net 本项目的技术栈 本项目技术栈基于 ES6、vue3、pinia、vue-router 、vite 、axios 和 element-plus http:/…

6.C++程序中的基本数据类型

数据类型是指在C中用于声明不同类型变量或函数的一个系统或抽象或者是一个分类&#xff0c;它决定了变量存储占用的内存空间以及解析存储的位模式。其实数据类型可以理解为固定内存大小的别名&#xff0c;是创建变量的模具&#xff0c;具体使用哪种模具&#xff08;包括自定义&…

Python安装不再难!全平台保姆级教程带你轻松搞定!

Python介绍 Python是一种功能强大且灵活的编程语言&#xff0c;被广泛应用于各个领域。以下是Python在不同应用领域的一些常见用途&#xff1a; 网络开发 Python提供了丰富的库和框架&#xff0c;使其成为网络开发的理想选择。诸如Django、Flask和Pyramid等框架可以帮助开发人员…

一张图解析FastAdmin中的表格列表(bootstrap-table)的功能(备份)

功能描述 请根据图片上的数字索引查看对应功能说明。 1.菜单名称和描述 默认生成的CRUD是没有菜单名称和描述显示的&#xff0c;如果需要显示则可以修改权限管理->菜单规则&#xff0c;给对应菜单的添加上备注信息后即可显示&#xff0c;支持HTML 2.TAB过滤选项卡 在一键…

Linux之CentOS 7.9-Minimal部署Oracle 11g r2 安装实测验证(桌面模式)

前言: 发个之前的库存… Linux之CentOS 7.9-Minimal部署Oracle 11g r2 安装实测验证(桌面模式) 本次验证的是CentOS_7_Minimal-2009桌面模式来部署Oracle 11g r2,大家可根据自身环境及学习来了解。 环境:下载地址都给你们超链好了 1、Linux系统镜像包: 1.1 CentOS-7-x86_…

Linux 删除文件不释放空间问题处理

背景&#xff1a; 服务器磁盘空间已经达到100%&#xff0c;删除存放日志路径下的文件后&#xff0c;发现空间并未释放&#xff01; 原因&#xff1a;在linux系统中&#xff0c;通过rm删除文件将会从文件系统的文件夹结构上解除链接(unlink)然后删除&#xff0c;然而假设文件是被…

探索Python的Excel世界:openpyxl的魔法之旅

文章目录 探索Python的Excel世界&#xff1a;openpyxl的魔法之旅背景&#xff1a;为什么选择openpyxl&#xff1f;什么是openpyxl&#xff1f;如何安装openpyxl&#xff1f;简单的库函数使用方法场景应用&#xff1a;openpyxl在实际工作中的应用常见bug及解决方案总结 探索Pyth…

如何利用视觉分析实现扬尘检测

随着城市化和工业化进程的加速&#xff0c;扬尘污染已成为全球各大城市面临的环境问题之一。建筑施工、道路交通以及工业活动产生的扬尘不仅影响空气质量&#xff0c;严重时还会引发呼吸道疾病&#xff0c;威胁公众健康。传统的扬尘检测手段多为传感器、采样仪等设备&#xff0…

【Echarts】vue3打开echarts的正确方式

ECharts 是一个功能强大、灵活易用的数据可视化工具&#xff0c;适用于商业报表、数据分析、科研教育等多种场景。那么该如何优雅的使用Echarts呢? 这里以vue3为例。 安装echarts pnpm i echarts封装公用方法 // ts-nocheck import * as echarts from echarts; // 我们这里借…

【C++指南】inline内联函数详解

&#x1f493; 博客主页&#xff1a;倔强的石头的CSDN主页 &#x1f4dd;Gitee主页&#xff1a;倔强的石头的gitee主页 ⏩ 文章专栏&#xff1a;《C指南》 期待您的关注 目录 引言 C为什么引入了inline来替代C语言中的宏 inline的基本用法 定义inline函数 inline的优势与…

IO模型---BIO、NIO、IO多路复用、AIO详解

本篇将想给详细解释一下什么是BIO、NIO、IO多路复用以及AIO~ 同步的阻塞(BIO)和非阻塞(NIO)的区别 BIO&#xff1a;线程发来IO请求后&#xff0c;一直阻塞着IO线程&#xff0c;需要缓冲区这边数据准备好之后&#xff0c;才会进行下一步的操作。 举个&#x1f330;&#xff1…

HarmonyOS应用开发者基础认证

目录 一、判断二、单选三、多选 一、判断 1、HarmonyOS提供了基础的应用加固安全能力&#xff0c;包括混淆、加密和代码签名能力。正确 2、可以通过ohpm uninstall 指令下载指定的三方库。错误 3、支持模块化开发是指一个应用通常会包含多种功能&#xff0c;将不同的功能特性…

【读书笔记-《30天自制操作系统》-23】Day24

本篇内容依然比较简单&#xff0c;主要是优化窗口功能以及开发定时器应用程序。首先是优化窗口的切换功能&#xff0c;实现通过键盘和鼠标切换窗口&#xff0c;然后是实现通过鼠标关闭窗口。接着实现不同窗口输入状态的切换&#xff0c;最后是实现定时器的API与应用程序。 1.…

Windows Server2016多用户登录破解

使用场景 很多时候&#xff0c;公司开发和测试运维会同时登录同一台windows服务器进行查询、更新、维护等操作&#xff0c;本文就来介绍一下Windows2016配置多人远程桌面登录实现&#xff0c;感兴趣的可以了解一下。 操作流程 &#xff08;1&#xff09;首先桌面需要安装远程…

旅行社区应该如何规划?

近年来&#xff0c;旅游行业逐渐恢复&#xff0c;包括微度假、精致露营、康养旅游、乡村民宿等旅游模式。用户旅游支出、旅游人次逐渐恢复&#xff0c;旅游收入仍待提升。 那么旅游社区应该如何搭建&#xff0c;内容如何规划呢&#xff1f; 我们了解到&#xff0c;很多旅游网…

kettle 数据库迁移 使用分页原理实现 数据库mysql

使用 kettle 9.0 先修改配置文件: C:\Users\xx\.kettle 新增如下配置,解决mysql 空字符串 自动转 null bug KETTLE_EMPTY_STRING_DIFFERS_FROM_NULLY git地址: GitHub - 2292011451/kettle_tool 第一步: 先把要迁移的表进行读取,循环查询每个表的最大数量以及页数,追加到…

ROS 设置dhcp option 6 多个地址格式

ROS routeOS 手工设置 dhcp 服务 option 6 多个dns 地址格式。字符串方式

机器学习(西瓜书)第 14 章 概率图模型

14.1 隐马尔可夫模型 机器学习最重要的任务&#xff0c;是根据一些已观察到的证据&#xff08;例如训练样本&#xff09;来对感兴趣的未知变量&#xff08;例如类别标记&#xff09;进行估计和推测。概率模型&#xff08;probabilistic model&#xff09;提供了一种描述框架&a…

动态线程池(四)

动态线程池 dtp生命周期管理 生命周期相关类图 DtpExecutor EagerEtpExecutor OrderedDtpExecutor TaskWrapper任务包装器 MdcRunnable TaskWrappers NotifyEnum NoticeManager通知管理器 InvokerChain调用链