当前位置: 首页 > 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.…...

手游刚开服就被攻击怎么办?如何防御DDoS?

开服初期是手游最脆弱的阶段&#xff0c;极易成为DDoS攻击的目标。一旦遭遇攻击&#xff0c;可能导致服务器瘫痪、玩家流失&#xff0c;甚至造成巨大经济损失。本文为开发者提供一套简洁有效的应急与防御方案&#xff0c;帮助快速应对并构建长期防护体系。 一、遭遇攻击的紧急应…...

TDengine 快速体验(Docker 镜像方式)

简介 TDengine 可以通过安装包、Docker 镜像 及云服务快速体验 TDengine 的功能&#xff0c;本节首先介绍如何通过 Docker 快速体验 TDengine&#xff0c;然后介绍如何在 Docker 环境下体验 TDengine 的写入和查询功能。如果你不熟悉 Docker&#xff0c;请使用 安装包的方式快…...

(十)学生端搭建

本次旨在将之前的已完成的部分功能进行拼装到学生端&#xff0c;同时完善学生端的构建。本次工作主要包括&#xff1a; 1.学生端整体界面布局 2.模拟考场与部分个人画像流程的串联 3.整体学生端逻辑 一、学生端 在主界面可以选择自己的用户角色 选择学生则进入学生登录界面…...

DockerHub与私有镜像仓库在容器化中的应用与管理

哈喽&#xff0c;大家好&#xff0c;我是左手python&#xff01; Docker Hub的应用与管理 Docker Hub的基本概念与使用方法 Docker Hub是Docker官方提供的一个公共镜像仓库&#xff0c;用户可以在其中找到各种操作系统、软件和应用的镜像。开发者可以通过Docker Hub轻松获取所…...

【位运算】消失的两个数字(hard)

消失的两个数字&#xff08;hard&#xff09; 题⽬描述&#xff1a;解法&#xff08;位运算&#xff09;&#xff1a;Java 算法代码&#xff1a;更简便代码 题⽬链接&#xff1a;⾯试题 17.19. 消失的两个数字 题⽬描述&#xff1a; 给定⼀个数组&#xff0c;包含从 1 到 N 所有…...

从零实现STL哈希容器:unordered_map/unordered_set封装详解

本篇文章是对C学习的STL哈希容器自主实现部分的学习分享 希望也能为你带来些帮助~ 那咱们废话不多说&#xff0c;直接开始吧&#xff01; 一、源码结构分析 1. SGISTL30实现剖析 // hash_set核心结构 template <class Value, class HashFcn, ...> class hash_set {ty…...

是否存在路径(FIFOBB算法)

题目描述 一个具有 n 个顶点e条边的无向图&#xff0c;该图顶点的编号依次为0到n-1且不存在顶点与自身相连的边。请使用FIFOBB算法编写程序&#xff0c;确定是否存在从顶点 source到顶点 destination的路径。 输入 第一行两个整数&#xff0c;分别表示n 和 e 的值&#xff08;1…...

【从零学习JVM|第三篇】类的生命周期(高频面试题)

前言&#xff1a; 在Java编程中&#xff0c;类的生命周期是指类从被加载到内存中开始&#xff0c;到被卸载出内存为止的整个过程。了解类的生命周期对于理解Java程序的运行机制以及性能优化非常重要。本文会深入探寻类的生命周期&#xff0c;让读者对此有深刻印象。 目录 ​…...

Visual Studio Code 扩展

Visual Studio Code 扩展 change-case 大小写转换EmmyLua for VSCode 调试插件Bookmarks 书签 change-case 大小写转换 https://marketplace.visualstudio.com/items?itemNamewmaurer.change-case 选中单词后&#xff0c;命令 changeCase.commands 可预览转换效果 EmmyLua…...

Vue 3 + WebSocket 实战:公司通知实时推送功能详解

&#x1f4e2; Vue 3 WebSocket 实战&#xff1a;公司通知实时推送功能详解 &#x1f4cc; 收藏 点赞 关注&#xff0c;项目中要用到推送功能时就不怕找不到了&#xff01; 实时通知是企业系统中常见的功能&#xff0c;比如&#xff1a;管理员发布通知后&#xff0c;所有用户…...