当前位置: 首页 > news >正文

算法笔记(十五)—— 动态规划(暴力递归到动态规划)习题训练!

通过递归到记忆化搜索再到严格表结构的动态规划

递归方法的评价:1. 单可变参数的维度;2. 可变参数的个数

记忆化搜索

在暴力递归中会存在很多的重复计算,可以使用存储结构来实现空间换时间。

严格表结构的动态规划

整理位置之间的依赖关系来达到进一步优化的效果。

322. 零钱兑换 - 力扣(LeetCode)https://leetcode.cn/problems/coin-change/

class Solution {
public:int coinChange(vector<int>& coins, int amount) {vector<int> count(amount+1 ,amount+1);count[0] = 0;for(auto coin : coins){for(int i = coin ; i<=amount ; i++){count[i] = min(count[i] , count[i-coin]+1);}}return count[amount]==amount+1?-1:count[amount];}
};

518. 零钱兑换 II - 力扣(LeetCode)https://leetcode.cn/problems/coin-change-ii/

class Solution {
public:int change(int amount, vector<int>& coins) {vector<int> count(amount+1 , 0);count[0] = 1;for(auto coin : coins){for(int i = coin ; i<=amount ; i++){count[i] += count[i-coin];}}return count[amount];}
};

剑指 Offer 42. 连续子数组的最大和 - 力扣(LeetCode)icon-default.png?t=N176https://leetcode.cn/problems/lian-xu-zi-shu-zu-de-zui-da-he-lcof/?envType=study-plan&id=lcof&plan=lcof&plan_progress=jkqqk9t

class Solution {
public:int maxSubArray(vector<int>& nums) {int res = nums[0] , pre = 0;for(auto &num : nums){pre = max(pre+num , num);res = max(res , pre);}return res;}
};

剑指 Offer 47. 礼物的最大价值 - 力扣(LeetCode)icon-default.png?t=N176https://leetcode.cn/problems/li-wu-de-zui-da-jie-zhi-lcof/?envType=study-plan&id=lcof&plan=lcof&plan_progress=jkqqk9t

// class Solution {
// public:
//     int process(vector<vector<int>>& grid , int x , int y , vector<vector<int>>& dp){
//         if(x==grid.size()||y==grid[0].size())return 0;
//         if(dp[x][y]!=0)return dp[x][y];
//         dp[x][y] = grid[x][y] + max(process(grid, x+1, y, dp), process(grid, x, y+1, dp));
//         return dp[x][y];
//     }//     int maxValue(vector<vector<int>>& grid) {
//         vector<vector<int>> dp(grid.size() , vector<int>(grid[0].size() , 0));
//         return process(grid, 0, 0, dp);
//     }
// };class Solution {
public:int maxValue(vector<vector<int>>& grid) {vector<int> dp(grid[0].size()+1 , 0);for(int i = grid.size()-1 ; i>=0 ; i--){for(int j = dp.size()-2 ; j>=0 ; j--){dp[j] = max(dp[j] , dp[j+1]) + grid[i][j];}}return dp[0];}
};

相关文章:

算法笔记(十五)—— 动态规划(暴力递归到动态规划)习题训练!

通过递归到记忆化搜索再到严格表结构的动态规划 递归方法的评价&#xff1a;1. 单可变参数的维度&#xff1b;2. 可变参数的个数 记忆化搜索 在暴力递归中会存在很多的重复计算&#xff0c;可以使用存储结构来实现空间换时间。 严格表结构的动态规划 整理位置之间的依赖关系…...

云原生架构基础概念及应用办法

什么是云原生&#xff1f; 云原生是一种基于容器、微服务和自动化运维的软件开发和部署方法。它可以使应用程序更加高效、可靠和可扩展&#xff0c;适用于各种不同的云平台。 如果要更直接通俗的来解释下上面的概念。 云原生更准确来说就是一种文化&#xff0c;是一种潮流&a…...

RedisTemplate 的基本使用手把手教

下载实例源码 使用步骤 1、引入 spring-boot-starter-data-redis 依赖 <dependency><groupId>org.springframework.boot</groupId><artifactId>spring-boot-starter-data-redis</artifactId> </dependency>2、在 application.yml 配置 R…...

Hbase -- Compact工具梳理

1. 背景 当前&#xff0c;线上HBase集群的自动Major Compact是关闭的&#xff0c;我们选择在凌晨业务空闲的时候进行手动触发Major Compact&#xff0c;Compact工具就是在运维平台上对资源组、RS、表进行Major Compact。目前线上有2种版本的Compact程序&#xff1a;Compact_v1…...

【java代码审计】SQL注入

1 原理 没有正确的对用户的输入进行检查&#xff0c;将用户的输入以拼接的方式带入到SQL语句中&#xff0c;导致SQL注入。 2 产生SQL注入的原因 2.1 JDBC拼接不当造成SQL注入 前置知识&#xff1a; JDBC执行SQL语句的两种方式&#xff1a; PrepareStatement&#xff1a;会对…...

前置知识-辛 Runge-Kutta 方法

1.3.3 辛 Runge-Kutta 方法 将方程 ( 1.10.2 ) (1.10 .2) (1.10.2) 改写为 d z d x =...

require 与 import 两种引入模块方式到底有什么区别?

关于JavaScript 的模块化规范&#xff0c;可以移步至&#xff1a; 【JavaScript高级】模块化规范「一文让你彻底搞懂前端模块化规范 & 区别」 下面进入正题 require 与 import 两种引入模块方式&#xff0c;到底有什么区别呢&#xff1f; 大致可以分为以下几个方面&#…...

软考信息系统监理师备考建议

用好备考方法&#xff0c;两三个月就可以过的。信息系统监理师备考最好以教材和历年真题为主&#xff0c;教学视频模拟题为辅。考试介绍与复习建议&#xff1a;考试设置的科目包括&#xff1a;&#xff08;1&#xff09;信息系统工程监理基础知识&#xff0c;考试时间150分钟&a…...

第八届蓝桥杯省赛——4承压计算(二维数组,嵌套循环)

题目&#xff1a;X星球的高科技实验室中整齐地堆放着某批珍贵金属原料。每块金属原料的外形、尺寸完全一致&#xff0c;但重量不同。金属材料被严格地堆放成金字塔形。7 5 8 7 8 8 9 2 7 2 8 1 4 9 1 8 1 8 8 4 1 7 9 6 1 4 5 4 5 6 5 5 6 9 5 6 5 5 4 7 9 3 5 5 1 7 5 7 9 7 4…...

【ECNU】3645. 莫干山奇遇(C++)

目录 题目 输入格式 输出格式 样例 提示 思路 代码 题目 单点时限: 2.0 sec 内存限制: 512 MB 出题人当然是希望出的题目有关 oxx&#xff0c;于是想方设法给题目配上一些有关 oxx 的背景故事&#xff0c;使得它看起来不那么无趣。但有的时候却无法引入合适的小姐姐&…...

为什么需要学习shell、shell的作用

课程基于B站于超课程笔记 03 Shebang的正确玩法_哔哩哔哩_bilibili P1 shell的作用 P2 shell执行命令的流程 P3 Shebang的正确玩法 什么是shell及组成 shell概念 shelll组成 Shebang概念 /bin/sh /bin/bash一样&#xff0c;都是指向一个bash解释器 [rootlocalhost ~]#…...

pgsql-Create_ALTER_GRANT_REVOKE命令语法

pgsql-Create_ALTER_GRANT_REVOKE命令语法 资料 语法约定 CREATE ROLE ALTER ROLE GRANT授权 REVOKE回收授权 权限类型说明 语法约定 下面的约定被用于命令的大纲&#xff1a;方括弧&#xff08;[和]&#xff09;表示可选的部分&#xff08;在 Tcl 命令里&#xff0c;使…...

【linux】:进程概念

文章目录 冯诺依曼体系结构一&#xff1a;操作系统二: 进程总结冯诺依曼体系结构 我们常见的计算机&#xff0c;如笔记本。我们不常见的计算机&#xff0c;如服务器&#xff0c;大部分都遵守冯诺依曼体系。 冯诺依曼体系如下图&#xff1a; 那么输入设备有哪些呢&#xff1f…...

创建对象的方式和对属性的操作

javaScript支持多种编程范式&#xff0c;包括函数式编程和面向对象编程&#xff0c;javaScript的对象被设计成一组属性的无序集合&#xff0c;由key和value组成。 创建对象的两种方式 早期使用创建对象方式最多的是使用Object类&#xff0c;使用new关键字来创建一个对象&…...

GO时间相关操作说明

文章目录 GO时间相关操作时间转换成字符串字符串转换成时间时间戳和时间操作时间比较操作时间增加和减少操作休眠操作time.AfterFunc操作time.NewTicker操作GO时间相关操作 ​ GO语言在使用时间转换的时候会用到2006-01-02 15:04:05 这是固定参数写法,类似java语言中的yyyy-M…...

选择和分支结构

选择和分支结构选择和分支结构一、复习问答二、选择结构2.1 基础选择结构2.2 if-else结构2.3 多重if结构2.4 嵌套if结构三、分支结构四、局部变量选择和分支结构 一、复习问答 1、Java中基本数据类型 2、类型的转换的两种情形 3、数据类型提升的规则 二、选择结构 2.1 基础选…...

Elasticsearch总结笔记

文章目录简介类型增删改查操作索引原理简介 底层使用的lucene引擎&#xff0c;lucene引擎直接使用相对复杂&#xff0c;有一定的学习成本&#xff0c;同样是使用Java编写&#xff0c;Elasticsearch使用的rest风格的进行交互&#xff0c;而数据呢则是以JSON的方式进行传输。学习…...

Ubuntu 安装指定版本 Mysql,并设置远程连接(以安装mysql 5.5 为例)

目录 一、安装Mysql 1、卸载Mysql&#xff08;可跳过&#xff09; 2、安装mysql 软件源 3、安装mysql 5.5 4、验证测试 二、设置远程登录 1、允许使用root账号远程连接 2、Mysql 允许远程登录 一、安装Mysql 1、卸载Mysql&#xff08;可跳过&#xff09; 如果之前安装…...

NumPy:Python中的强大数学工具

NumPy&#xff1a;Python中的强大数学工具 文章目录NumPy&#xff1a;Python中的强大数学工具一、NumPy简介二、创建数组三、数组尺寸四、数组运算五、数组切片六、数组连接七、数据存取八、数组形态变换九、数组排序与搜索十、矩阵与线性代数运算一、NumPy简介 当谈到数据科学…...

Hbase资源隔离操作指南

1.检查集群的环境配置 1.1 HBase版本号确认> 5.11.0 引入rsgroup的Patch&#xff1a; [HBASE-6721] RegionServer Group based Assignment - ASF JIRA RegionServer Group based Assignment 社区支持版本&#xff1a;2.0.0 引入rsgroup的CDH版本 5.11.0 https://www.…...

进程地址空间(比特课总结)

一、进程地址空间 1. 环境变量 1 &#xff09;⽤户级环境变量与系统级环境变量 全局属性&#xff1a;环境变量具有全局属性&#xff0c;会被⼦进程继承。例如当bash启动⼦进程时&#xff0c;环 境变量会⾃动传递给⼦进程。 本地变量限制&#xff1a;本地变量只在当前进程(ba…...

AI Agent与Agentic AI:原理、应用、挑战与未来展望

文章目录 一、引言二、AI Agent与Agentic AI的兴起2.1 技术契机与生态成熟2.2 Agent的定义与特征2.3 Agent的发展历程 三、AI Agent的核心技术栈解密3.1 感知模块代码示例&#xff1a;使用Python和OpenCV进行图像识别 3.2 认知与决策模块代码示例&#xff1a;使用OpenAI GPT-3进…...

电脑插入多块移动硬盘后经常出现卡顿和蓝屏

当电脑在插入多块移动硬盘后频繁出现卡顿和蓝屏问题时&#xff0c;可能涉及硬件资源冲突、驱动兼容性、供电不足或系统设置等多方面原因。以下是逐步排查和解决方案&#xff1a; 1. 检查电源供电问题 问题原因&#xff1a;多块移动硬盘同时运行可能导致USB接口供电不足&#x…...

【项目实战】通过多模态+LangGraph实现PPT生成助手

PPT自动生成系统 基于LangGraph的PPT自动生成系统&#xff0c;可以将Markdown文档自动转换为PPT演示文稿。 功能特点 Markdown解析&#xff1a;自动解析Markdown文档结构PPT模板分析&#xff1a;分析PPT模板的布局和风格智能布局决策&#xff1a;匹配内容与合适的PPT布局自动…...

Springcloud:Eureka 高可用集群搭建实战(服务注册与发现的底层原理与避坑指南)

引言&#xff1a;为什么 Eureka 依然是存量系统的核心&#xff1f; 尽管 Nacos 等新注册中心崛起&#xff0c;但金融、电力等保守行业仍有大量系统运行在 Eureka 上。理解其高可用设计与自我保护机制&#xff0c;是保障分布式系统稳定的必修课。本文将手把手带你搭建生产级 Eur…...

OpenLayers 分屏对比(地图联动)

注&#xff1a;当前使用的是 ol 5.3.0 版本&#xff0c;天地图使用的key请到天地图官网申请&#xff0c;并替换为自己的key 地图分屏对比在WebGIS开发中是很常见的功能&#xff0c;和卷帘图层不一样的是&#xff0c;分屏对比是在各个地图中添加相同或者不同的图层进行对比查看。…...

如何在最短时间内提升打ctf(web)的水平?

刚刚刷完2遍 bugku 的 web 题&#xff0c;前来答题。 每个人对刷题理解是不同&#xff0c;有的人是看了writeup就等于刷了&#xff0c;有的人是收藏了writeup就等于刷了&#xff0c;有的人是跟着writeup做了一遍就等于刷了&#xff0c;还有的人是独立思考做了一遍就等于刷了。…...

【Nginx】使用 Nginx+Lua 实现基于 IP 的访问频率限制

使用 NginxLua 实现基于 IP 的访问频率限制 在高并发场景下&#xff0c;限制某个 IP 的访问频率是非常重要的&#xff0c;可以有效防止恶意攻击或错误配置导致的服务宕机。以下是一个详细的实现方案&#xff0c;使用 Nginx 和 Lua 脚本结合 Redis 来实现基于 IP 的访问频率限制…...

CVPR2025重磅突破:AnomalyAny框架实现单样本生成逼真异常数据,破解视觉检测瓶颈!

本文介绍了一种名为AnomalyAny的创新框架&#xff0c;该方法利用Stable Diffusion的强大生成能力&#xff0c;仅需单个正常样本和文本描述&#xff0c;即可生成逼真且多样化的异常样本&#xff0c;有效解决了视觉异常检测中异常样本稀缺的难题&#xff0c;为工业质检、医疗影像…...

Vue 模板语句的数据来源

&#x1f9e9; Vue 模板语句的数据来源&#xff1a;全方位解析 Vue 模板&#xff08;<template> 部分&#xff09;中的表达式、指令绑定&#xff08;如 v-bind, v-on&#xff09;和插值&#xff08;{{ }}&#xff09;都在一个特定的作用域内求值。这个作用域由当前 组件…...