【C++刷题】优选算法——递归第四辑

news/2024/7/25 2:39:13/文章来源:https://blog.csdn.net/weixin_62172209/article/details/139157599

记忆化搜索篇

  • 什么是记忆化搜索?
    • 带 备忘录 的递归
  • 如何实现记忆化搜索?
    • a.添加一个备忘录 <可变参数,返回值>
    • b.每次递归返回的时候,把结果放到备忘录里
    • c.每次递归进入的时候,先查看一下备忘录
  • 记忆化搜索 vs 常规动态规划:
    • 相同点:
      • 都是暴力解法(暴搜)
      • 优化方式都是把已经计算出的结果存起来
    • 不同点:
      • 记忆化搜索是递归形式
      • 常规动态规划是递推(循环)形式

问题:

  • 所有的递归(暴搜、深搜),都能改成记忆化搜索吗?
    不是的。 只有在递归的过程中,出现了大量完全相同的问题时,才能用记忆化搜索的方式优化。
  • 以 暴搜->记忆化搜索->动态规划 的流程思路来解决动态规划问题,一定程度上是可行的。暴搜的阶段也可以为确定状态表示,提供一个参考方向。
  1. 斐波那契数
// 1 - 递归
int dfs(int n)
{if(n == 0 || n == 1) return n;return dfs(n-1) + dfs(n-2);
}
int fib(int n)
{return dfs(n);
}// 2 - 记忆化搜索
unordered_map<int, int> memo; // 创建备忘录
int dfs(int n)
{if(n == 0 || n == 1){if(!memo.count(n)) memo[n] = n; // 返回之间添加备忘录return n;}if(memo.count(n)) return memo[n]; // 进入之前查看备忘录else{memo[n] = dfs(n-1) + dfs(n-2);return memo[n];}}
int fib(int n)
{return dfs(n);
}// 3 - 动态规划
int fib(int n)
{// 0.预处理if(n == 0 || n == 1) return n;// 1.dp数组vector<int> dp(n + 1, 0);// 2.初始化dp[1] = 1;// 3.状态转移方程for(int i = 2; i < dp.size(); ++i){dp[i] = dp[i-1] + dp[i-2];}// 4.返回值return dp.back();
}
  1. 不同路径
// 1 - 记忆化搜索
vector<vector<int>> memo;
int dfs(int i, int j)
{if(i == 0 || j == 0){memo[i][j] = 1;return 1;}if(memo[i][j] == 0) memo[i][j] = dfs(i - 1, j) + dfs(i, j - 1);return memo[i][j];
}
int uniquePaths(int m, int n)
{memo = vector<vector<int>>(m, vector<int>(n, 0));return dfs(m-1, n-1);
}// 2 - 动态规划
int uniquePaths(int m, int n)
{// 1.dp数组vector<vector<int>> dp(m, vector<int>(n));// 2.初始化for (int i = 0; i < m; ++i){dp[i][0] = 1;}for (int i = 0; i < n; ++i){dp[0][i] = 1;}// 3.状态转移方程for (int row = 1; row < m; ++row){for (int col = 1; col < n; ++col){dp[row][col] = dp[row - 1][col] + dp[row][col - 1];}}// 4.返回值return dp.back().back();
}
  1. 最长递增子序列
vector<int> memo;
int dfs(vector<int>& nums, int step)
{if(memo[step] != 0) return memo[step];int ret = 1;for(int i = step + 1; i < nums.size(); ++i){if(nums[i] > nums[step]){ret = max(ret, dfs(nums, i) + 1);}}memo[step] = ret;return ret;
}
int lengthOfLIS(vector<int>& nums)
{memo = vector<int>(nums.size(), 0);int ret = 0;for(int i = 0; i < nums.size(); ++i){ret = max(ret, dfs(nums, i));}return ret;
}
  1. 猜数字大小 II
vector<vector<int>> memo;
int dfs(int start, int end)
{if(start >= end) return 0;if(memo[start][end] != -1) return memo[start][end];int ret = INT_MAX;for(int i = start; i <= end; ++i){ret = min(ret, i + max(dfs(start, i - 1), dfs(i + 1, end)));}memo[start][end] = ret;return ret;
}
int getMoneyAmount(int n)
{memo = vector<vector<int>>(n+1, vector<int>(n+1, -1));return dfs(1, n);
}
  1. 矩阵中的最长递增路径
unordered_multimap<int, int> direction = {{0, 1},{0, -1},{1, 0},{-1, 0}
};
vector<vector<int>> memo;
int dfs(vector<vector<int>>& matrix, int i, int j)
{if(memo[i][j] != -1) return memo[i][j];int ret = 0;for(auto& e : direction){int x = i + e.first, y = j + e.second;if((x >= 0 && x < matrix.size())&& (y >= 0 && y < matrix[0].size())&& (matrix[x][y] > matrix[i][j])){ret = max(ret, 1 + dfs(matrix, x, y));}}memo[i][j] = ret;return ret;
}
int longestIncreasingPath(vector<vector<int>>& matrix)
{int m = matrix.size();int n = matrix[0].size();memo = vector<vector<int>>(m, vector<int>(n, -1));int ret = 0;for(int i = 0; i < m; ++i){for(int j = 0; j < n; ++j){ret = max(ret, 1 + dfs(matrix, i, j));}}return ret;
}

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

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

相关文章

斯洛文尼亚普利雅玛城堡:吉尼斯世界纪录认证的世界最大溶洞城堡

除了著名的波斯托伊纳溶洞&#xff08;Postojna Cave&#xff09;&#xff0c;普利雅玛城堡&#xff08;Predjama Castle&#xff09;也是波斯托伊纳洞穴公园&#xff08;Postojna Cave Park&#xff09;不容错过的景点之一。这座城堡坐落在斯洛文尼亚&#xff08;Slovenia&…

Java入门基础学习笔记47——ArrayList

什么是集合呢&#xff1f; 集合是一种容器&#xff0c;用来装数据的&#xff0c;类似数组。 有数组&#xff0c;为什么还要学习集合呢&#xff1f; 数组定义完成并启动后&#xff0c;长度就固定了。 而集合是大小可变&#xff0c;开发中用的最多的。 集合的特点&#xff1a;大…

基于docxtpl的模板生成Word

docxtpl是一个用于生成Microsoft Word文档的模板引擎库。它结合了docx模块和Jinja2模板引擎&#xff0c;使用户能够使用Microsoft Word模板文件并在其中填充动态数据。这个库提供了一种方便的方式来生成个性化的Word文档&#xff0c;并支持条件语句、循环语句和变量等控制结构&…

从零开始构建 Vision Transformer(ViT) 模型

Transformer 模型最早由 Vaswani 等人在 2017 年论文 Attention Is All You Need 中提出&#xff0c;并已广泛应用于自然语言处理。 2021年&#xff0c;Dosovitsky 等人在论文An Image is Worth 16x16 Words: Transformers for Image Recognition at Scale中提出将 Transforme…

PyQt5-新手避坑指南(持续更新)

文章目录 一&#xff0e;前言二&#xff0e;开发环境三&#xff0e;坑1.程序没有详细报错就退出了2.qrc资源文件的使用3.QLabel文字自动换行4.图片自适应大小5.checkbox自定义样式后✓不见了6.多线程 四&#xff0e;记录 一&#xff0e;前言 本篇博客整理了一些初学者容易犯的…

211大学计算机专业不考408,新增的交叉专业却考408!南京农业大学计算机考研考情分析!

南京农业大学信息科技学院可追溯至1981年成立的计算中心和1985年筹建的农业图书情报专业。1987年设立了农业图书情报系&#xff0c;1993 年农业图书情报系更名为信息管理系&#xff0c;本科专业名称也于1999年更名为信息管理与信息系统专业。1994年计算中心开始招收计算机应用专…

YOLOv10来了

B站&#xff1a;啥都会一点的研究生公众号&#xff1a;啥都会一点的研究生 前言 YOLOv10 由清华大学研究人员在 Ultralytics版基础上进行进一步开发&#xff0c;引入了一种新的实时目标检测方法&#xff0c;解决了以前版本 YOLO 在后处理和模型架构方面的不足。通过消除非最大…

英码科技算能系列边缘计算盒子再添新成员!搭载TPU处理器BM1688CV186AH,功耗更低、接口更丰富

在数据呈现指数级增长的今天&#xff0c;越来越多的领域和细分场景对实时、高效的数据处理和分析的需求日益增长&#xff0c;对智能算力的需求也不断增强。为应对新的市场趋势&#xff0c;英码科技凭借自身的硬件研发优势&#xff0c;携手算能相继推出了基于BM1684的边缘计算盒…

探索循环逻辑:for逻辑分支与容器遍历的深度剖析

新书上架~&#x1f447;全国包邮奥~ python实用小工具开发教程http://pythontoolsteach.com/3 欢迎关注我&#x1f446;&#xff0c;收藏下次不迷路┗|&#xff40;O′|┛ 嗷~~ 目录 一、引言&#xff1a;for逻辑与循环体的奥秘 二、for逻辑与循环体的结合使用 1. 函数与循环…

数字水印 | 离散余弦变换 DCT 基本原理及 Python 代码实现

目录 1 基本原理2 代码实现3 图像压缩 1 基本原理 参考博客&#xff1a;https://www.cnblogs.com/zxporz/p/16072580.html D C T \mathsf{DCT} DCT 全称为 D i s c r e t e C o s i n e T r a n s f o r m \mathsf{Discrete\ Cosine\ Transform} Discrete Cosine Transfo…

Git远程控制

文章目录 1. 创建仓库1.1 Readme1.2 Issue1.3 Pull request 2. 远程仓库克隆3. 推送远程仓库4. 拉取远程仓库5. 配置Git.gitignore配置别名 使用GitHub可以&#xff0c;采用Gitee也行 1. 创建仓库 1.1 Readme Readme文件相当于这个仓库的说明书&#xff0c;gitee会初始化2两份…

字符串的周期:每一期都有那么几位

【题目描述】 如果一个字符串可以由某个长度为k的字符串重复多次得到,则称该串以k为周期。例 如,abcabcabcabc以3为周期(注意,它也以6和12为周期)。 输入一个长度不超过80的字符串(不含空格),输出其最小周期。 输入第一行表示有T组数据,后续是T行字符串。输出的每组…

打印机里失败的任务删不掉的解决办法 斑马打印机更新电脑驱动和升级打印机固件 提示ribbon out 并黄状态亮+黄供应闪

强删打印任务 WinR services.msc 停止服务 Print spooler C:\Windows\System32\spool\PRINTERS 清空文件夹下所有文件 详细 要删除打印机里失败的任务&#xff0c;可以按照以下步骤操作&#xff1a; 停止打印服务&#xff1a;您需要停止Windows系统中的“Print Spooler”服…

期货学习笔记-斐波那契学习1

斐波那契数列介绍 斐波那契数列是1、1、2、3、5、8、13、21、34、55、89…据说这是数学家莱昂纳多 斐波那契研究兔子繁殖时发现的一个神奇数列&#xff0c;似乎大自然在按照这个数列进行演化&#xff0c;一个斐波那契数字是由该数列相邻的前两个数字相加得到的 在斐波那契交易…

亚马逊云主管马特·加尔曼面临压力,致力于在人工智能领域赶超竞争对手

每周跟踪AI热点新闻动向和震撼发展 想要探索生成式人工智能的前沿进展吗&#xff1f;订阅我们的简报&#xff0c;深入解析最新的技术突破、实际应用案例和未来的趋势。与全球数同行一同&#xff0c;从行业内部的深度分析和实用指南中受益。不要错过这个机会&#xff0c;成为AI领…

如果任务过多,队列积压怎么处理?

如果任务过多,队列积压怎么处理? 1、内存队列满了应该怎么办2、问题要治本——发短信导致吞吐量降低的问题不能忽略!!3、多路复用IO模型的核心组件简介1、内存队列满了应该怎么办 如图: 大家可以看到,虽然现在发短信和广告投递,彼此之间的执行效率不受彼此影响,但是请…

架构方案演进

1、架构方案演进 一、架构 1、单体架构 2、垂直化拆分 3、集群负载均衡 4、SOA架构 5、微服务架构 6、服务网格 绿色方块为应用服务&#xff0c;蓝色方块为Sidecar Proxy&#xff0c;应用服务之间通过Sidecar Proxy进行通信&#xff0c;整个服务通信形成蓝色网格连线&#xff…

如何做好服务器数据防泄密

在数字化时代&#xff0c;服务器数据的安全与保密性对于企业而言至关重要。数据泄露不仅可能导致经济损失&#xff0c;还可能损害声誉和客户关系。因此&#xff0c;做好服务器数据防泄露工作显得尤为重要。 首先&#xff0c;加强安全意识是防止数据泄露的首要任务。企业需要认识…

【ArcGIS微课1000例】0112:沿线(面)按距离或百分比生成点

文章目录 一、沿线生成点工具介绍二、线状案例三、面状案例一、沿线生成点工具介绍 位置:工具箱→数据管理工具→采样→沿线生成点 摘要:沿线或面以固定间隔或百分比创建点要素。 用法:输入要素的属性将保留在输出要素类中。向输出要素类添加新字段 ORIG_FID,并设置为输…

统信UOS专业版操作系统如何安装惠普打印机驱动

通用集成驱动安装方法 以惠普P1566激光打印机为例介绍一下&#xff0c;在打印机管理器中选择打印机&#xff0c;手动选择安装驱动&#xff0c;找到品牌&#xff1a;惠普&#xff0c;型号&#xff1a;1566&#xff0c;安装驱动后测试打印&#xff1b;LaserJet Pro P1566 Foomati…