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

递归到动态规划:省去枚举行为

如果在动态规划的过程中没有枚举行为,那严格位置依赖和傻缓存的方式并没有太大区别,但是当有枚举行为的时候(一个位置依赖于多个位置),那严格位置依赖是有优化空间的,枚举行为也许可以省去,题目:

arr是面值数组,其中的值都是正数且没有重复。再给定一个正数aim

每个值都认为是一种面值,且认为张数是无限的。

返回组成aim的方法数

例如:arr = {1,2}aim = 4

方法如下:1+1+1+11+1+22+2

一共就3种方法,所以返回3

这个题目的动态规划普遍位置({1,8})的依赖,我们原来dp[1][8] = dp [2][8] + dp[2][6] + dp[2][4] + dp[2][2] + dp[2][0]

而dp[1][6] = dp[2][6] + dp[2][4] + dp[2][2] + dp[2][0]

我们可以看到计算dp[2][8]时候用到的 dp[2][6] + dp[2][4] + dp[2][2] + dp[2][0]之前其实是计算过的,这个值就是dp[1][6]

所以可以简化为dp[1][6] + dp[2][8]

普遍位置就是dp[index][rest] = dp[index+1][rest] + dp[index][rest-arr[index]]

dp[index][rest-arr[index]]这个要先判断存在不存在

也就是它依赖于它的下方和左边,dp数组按照从下到上,从左到右的顺序初始化即可

 对应的代码如下:

package dataStructure.recurrence.practice;/*** arr是面值数组,其中的值都是正数且没有重复。再给定一个正数aim。* 每个值都认为是一种面值,且认为张数是无限的。* 返回组成aim的方法数* 例如:arr = {1,2},aim = 4* 方法如下:1+1+1+1、1+1+2、2+2* 一共就3种方法,所以返回3*/
public class CoinsWayNoLimit {public static int coinsWay(int[] arr, int aim) {return process1(arr, 0, aim);}/*** 动态规划的解法-原始版* 根据递归,可变的参数是index和rest,变化范围分别是0~arr.length, 0~rest* @param arr 原始的数组* @param aim 要组成的目标* @return*/public static int coinsWayDp(int[] arr, int aim) {int[][] dp = new int[arr.length + 1][aim + 1];//最后一行只有0位置是1,其他都是0(0是int默认值,不需要初始化)dp[arr.length][0] = 1;//根据递归,所有的(index, rest)都依赖于下一行前面的某个位置//所以行必须从下往上,列初始化的顺序无所谓for(int index = arr.length - 1; index >=0; index --) {for(int rest = 0; rest <= aim; rest ++) {int ways = 0;for(int num = 0; num * arr[index] <= rest; num ++) {ways += dp[index + 1][rest - (num * arr[index])];}dp[index][rest] = ways;}}return dp[0][aim];}/*** 动态规划的解法-原始版* 根据递归,可变的参数是index和rest,变化范围分别是0~arr.length, 0~rest* @param arr 原始的数组* @param aim 要组成的目标* @return*/public static int coinsWayDpBest(int[] arr, int aim) {int[][] dp = new int[arr.length + 1][aim + 1];//最后一行只有aim位置是1,其他都是0(0是int默认值,不需要初始化)dp[arr.length][0] = 1;//根据递归,所有的(index, rest)都依赖于下一行前面的某个位置//所以行必须从下往上,这里我们要省掉枚举行为,一个位置依赖于他下面的位置和他前面的某个位置,所以必须从前往后for(int index = arr.length - 1; index >=0; index --) {for(int rest = 0; rest <= aim; rest ++) {//这是倒数第二行,他下面肯定有位置dp[index][rest] = dp[index + 1][rest];//但是左边的位置rest-arr[index]不一定存在,所以要做判断if(rest-arr[index] >= 0) {//如果存在就加上dp[index][rest] += dp[index][rest-arr[index]];}}}return dp[0][aim];}/*** 递归黑盒方法,从index号下标开始组成left* @param arr 原始的面值数组,每个面值都是无限的* @param index 当前要考虑的位置下标* @param rest 还差多少钱* @return*/public static int process1(int[] arr, int index, int rest) {if(rest < 0) return 0;if(index == arr.length) {return rest == 0? 1 : 0;}int ways = 0;for(int num = 0; num * arr[index] <= rest; num++) {ways += process1(arr, index + 1, rest - (num * arr[index]));}return ways;}public static void main(String[] args) {int[] arr = {1,2};int aim = 4;int ways = coinsWay(arr, aim);System.out.println(ways);int waysDp1 = coinsWayDp(arr, aim);System.out.println(waysDp1);int waysDpBest = coinsWayDpBest(arr, aim);System.out.println(waysDpBest);}
}

省去了枚举行为,结果完全一致,原来的时间复杂度是O(N * M * K),现在的话变成了O(N * M)

其中K是rest/数组中最小的那个面值

个人的总结是:如果某个位置只依赖它的90度角范围内的枚举都是可以优化的(上、左  上、左上、左 等等)

欢迎私信讨论

相关文章:

递归到动态规划:省去枚举行为

如果在动态规划的过程中没有枚举行为&#xff0c;那严格位置依赖和傻缓存的方式并没有太大区别&#xff0c;但是当有枚举行为的时候&#xff08;一个位置依赖于多个位置&#xff09;&#xff0c;那严格位置依赖是有优化空间的&#xff0c;枚举行为也许可以省去&#xff0c;题目…...

服务(第二十一篇)mysql高级查询语句(二)

①视图表&#xff1a; 视图表是虚拟表&#xff0c;用来存储SQL语句的定义 如果视图表和原表的字段相同&#xff0c;是可以进行数据修改的&#xff1b; 如果两者的字段不通&#xff0c;不可以修改数据。 语法&#xff1a; 创建&#xff1a;create view 试图表名 as ... 查…...

MYSQL高可用配置(MHA)

1、什么是MHA MHA&#xff08;Master High Availability&#xff09;是一套优秀的MySQL高可用环境下故障切换和主从复制的软件。 MHA 的出现就是解决MySQL 单点的问题。 MySQL故障切换过程中&#xff0c;MHA能做到0-30秒内自动完成故障切换操作。 MHA能在故障切换的过程中最大…...

单精度浮点数与十进制数据相互转换

一、float基础&#xff1a; Float类型占4个字节,也就是32bit,其中最高位是符号位,2~9位是指数位,后边的23bit是数值位.如下所示 大部分数据的二进制形式都可以用科学计数法表示,即1.m*2^n这种形式,只要知道m和n,就能确定一个数值 二、小数位如何转变为二进制&#xff1a; 下面…...

PMP敏捷-4大价值观、12原则

宣言及4大价值观 个体及互动 胜于 流程和工具 以人为本 工作的软件 胜于 完整的文档 以价值为导向 客户合作 胜于 合同谈判 合作共赢 应对变更 胜于 遵循计划 拥抱变化 12原则 工作原则&#xff1a;精益、至简&#xff0c;实现这种原则的方式是“定期反省”。9、10、12 …...

K8S—Helm

一、Helm介绍 helm通过打包的方式&#xff0c;支持发布的版本管理和控制&#xff0c;很大程度上简化了Kubernetes应用的部署和管理。 Helm本质就是让k8s的应用管理&#xff08;Deployment、Service等&#xff09;可配置&#xff0c;能动态生成。通过动态生成K8S资源清单文件&a…...

ALSA内部函数调用流程

ALSA内部函数调用流程 一直都有这样的一个疑问 就是在linux系统中我们调用snd_pcm_open后&#xff0c;就不知道alsa内部是怎么运行的了 用户的pcm_open()相当于先对ASoC各个驱动模块startup()&#xff0c;再做hw_params()。 pcm_open()pcm->fd open("/dev/snd/pcm…...

Python正则表达式详解,保姆式教学,0基础也能掌握正则

正则作为处理字符串的一个实用工具&#xff0c;在Python中经常会用到&#xff0c;比如爬虫爬取数据时常用正则来检索字符串等等。正则表达式已经内嵌在Python中&#xff0c;通过导入re模块就可以使用&#xff0c;作为刚学Python的新手大多数都听说”正则“这个术语。 今天来给…...

ChatGPT 接入飞书教程,创建自己的聊天机器人

ChatGPT 接入飞书教程,创建自己的聊天机器人 一、飞书进入开发者平台。点击创建应用。二、打开Aircode,点击创建应用,上面输入名字,下面选择Node.js v16三、配置环境,点击Environments,创建四个变量,全部要大写本教程收集于: AIGC从入门到精通教程 首先,准备三个账号…...

JS生成随机数(多种解决方案)

JS生成随机数 概述 随机数是编程语言中的重要组成部分。在JavaScript中&#xff0c;生成随机数是一项简单的任务。本文将介绍生成随机数的各种方法。 Math.random() Math.random()是JavaScript中生成随机数最常见的方法。该方法返回介于0和1之间的随机数。例如&#xff0c;…...

文件IO 函数 静态库和动态库的创建 5.11

5.11 文件IO函数 1.数据读写 ssize_t read(int fd,void *buf,size_t count); 功能&#xff1a; ​ 从fd对应的文件中 读取前count个字节的数据到buf缓冲区中 头文件&#xff1a; ​ #include <unistd.h> 参数&#xff1a; ​ fd &#xff1a;文件描述符 ​ buf…...

考研日语-详解ている、てある、ていく、てくる用法

目录 一、ている用法 1. 表示现在状态 2. 表示持续动作 3. 表示经验或习惯 4. 表示结果或效果 二、てある用法 1. 表示已经完成的动作 2. 表示现在状态 3. 表示被动 三、ていく用法 1. 表示未来的动作 2. 表示逐渐变化的过程 四、てくる用法 1. 表示过去到现在的…...

Spring Security 6.x 系列【36】授权服务器篇之OpenID Connect 1.0

有道无术,术尚可求,有术无道,止于术。 本系列Spring Boot 版本 3.0.4 本系列Spring Security 版本 6.0.2 本系列Spring Authorization Server 版本 1.0.2 源码地址:https://gitee.com/pearl-organization/study-spring-security-demo 文章目录 1. 前言2. OpenID Connect…...

【计算机视觉 | Pytorch】timm 包的具体介绍和图像分类案例(含源代码)

一、具体介绍 timm 是一个 PyTorch 原生实现的计算机视觉模型库。它提供了预训练模型和各种网络组件&#xff0c;可以用于各种计算机视觉任务&#xff0c;例如图像分类、物体检测、语义分割等等。 timm 的特点如下&#xff1a; PyTorch 原生实现&#xff1a;timm 的实现方式…...

轻博客Plume的搭建

什么是 Plume &#xff1f; Plume 是一个基于 ActivityPub 的联合博客引擎。它是用 Rust 编写的&#xff0c;带有 Rocket 框架&#xff0c;以及 Diesel 与数据库交互。前端使用 Ructe模板、WASM 和SCSS。 反向代理 假设我们实际访问地址为&#xff1a; https://plume.laosu.ml…...

机器人关节电机PWM

脉冲宽度调制(Pulse width modulation,PWM)技术。一种模拟控制方式 机器人关节电机的控制通常使用PWM(脉冲宽度调制)技术。PWM是一种用于控制电子设备的技术,通过控制高电平和低电平之间的时间比例,实现对电子设备的控制。在机器人关节电机中,PWM信号可以控制电机的…...

MPU6050详解(含源码)

前言&#xff1a;MPU6050是一款强大的六轴传感器&#xff0c;需要理解MPU6050首先得有IIC的基础&#xff0c;MPU6050 内部整合了 3 轴陀螺仪和 3 轴加速度传感器&#xff0c;并且含有一个第二 IIC 接口&#xff0c;可用于连接外部磁力传感器&#xff0c;内部有硬件算法支持. 1…...

Vue入门学习笔记:TodoList(三):实例中的数据、事件和方法

目录&#xff1a; Vue入门学习笔记&#xff1a;TodoList&#xff08;一&#xff09;&#xff1a;HelloWorld Vue入门学习笔记&#xff1a;TodoList&#xff08;二&#xff09;&#xff1a;挂载点、模板、实例 Vue入门学习笔记&#xff1a;TodoList&#xff08;三&#xff09;&a…...

怎么找到引发回流的JavaScript代码?

要找到引发回流的JavaScript代码&#xff0c;可以使用浏览器的开发者工具中的性能分析器。不同的浏览器有不同的名称和位置&#xff0c;例如Google Chrome的开发者工具中的性能分析器被称为Performance&#xff0c;Firefox的开发者工具中的性能分析器被称为Profiler。 以下是在…...

未来广告策划,转型还是淘汰?

在广告行业呆了十来年了&#xff0c;最近我越来越感觉到广告行业真的是一个需要与时俱进&#xff0c;并且应用场景非常广泛的一个专业。 而且由于这是一个需要创意能力的行业&#xff0c;所以对比于重复性容易被机器以及人工智能所代替的岗位行业来说&#xff0c;广告的可替代…...

SpringBoot-17-MyBatis动态SQL标签之常用标签

文章目录 1 代码1.1 实体User.java1.2 接口UserMapper.java1.3 映射UserMapper.xml1.3.1 标签if1.3.2 标签if和where1.3.3 标签choose和when和otherwise1.4 UserController.java2 常用动态SQL标签2.1 标签set2.1.1 UserMapper.java2.1.2 UserMapper.xml2.1.3 UserController.ja…...

龙虎榜——20250610

上证指数放量收阴线&#xff0c;个股多数下跌&#xff0c;盘中受消息影响大幅波动。 深证指数放量收阴线形成顶分型&#xff0c;指数短线有调整的需求&#xff0c;大概需要一两天。 2025年6月10日龙虎榜行业方向分析 1. 金融科技 代表标的&#xff1a;御银股份、雄帝科技 驱动…...

linux之kylin系统nginx的安装

一、nginx的作用 1.可做高性能的web服务器 直接处理静态资源&#xff08;HTML/CSS/图片等&#xff09;&#xff0c;响应速度远超传统服务器类似apache支持高并发连接 2.反向代理服务器 隐藏后端服务器IP地址&#xff0c;提高安全性 3.负载均衡服务器 支持多种策略分发流量…...

通过Wrangler CLI在worker中创建数据库和表

官方使用文档&#xff1a;Getting started Cloudflare D1 docs 创建数据库 在命令行中执行完成之后&#xff0c;会在本地和远程创建数据库&#xff1a; npx wranglerlatest d1 create prod-d1-tutorial 在cf中就可以看到数据库&#xff1a; 现在&#xff0c;您的Cloudfla…...

STM32标准库-DMA直接存储器存取

文章目录 一、DMA1.1简介1.2存储器映像1.3DMA框图1.4DMA基本结构1.5DMA请求1.6数据宽度与对齐1.7数据转运DMA1.8ADC扫描模式DMA 二、数据转运DMA2.1接线图2.2代码2.3相关API 一、DMA 1.1简介 DMA&#xff08;Direct Memory Access&#xff09;直接存储器存取 DMA可以提供外设…...

汇编常见指令

汇编常见指令 一、数据传送指令 指令功能示例说明MOV数据传送MOV EAX, 10将立即数 10 送入 EAXMOV [EBX], EAX将 EAX 值存入 EBX 指向的内存LEA加载有效地址LEA EAX, [EBX4]将 EBX4 的地址存入 EAX&#xff08;不访问内存&#xff09;XCHG交换数据XCHG EAX, EBX交换 EAX 和 EB…...

MySQL JOIN 表过多的优化思路

当 MySQL 查询涉及大量表 JOIN 时&#xff0c;性能会显著下降。以下是优化思路和简易实现方法&#xff1a; 一、核心优化思路 减少 JOIN 数量 数据冗余&#xff1a;添加必要的冗余字段&#xff08;如订单表直接存储用户名&#xff09;合并表&#xff1a;将频繁关联的小表合并成…...

Razor编程中@Html的方法使用大全

文章目录 1. 基础HTML辅助方法1.1 Html.ActionLink()1.2 Html.RouteLink()1.3 Html.Display() / Html.DisplayFor()1.4 Html.Editor() / Html.EditorFor()1.5 Html.Label() / Html.LabelFor()1.6 Html.TextBox() / Html.TextBoxFor() 2. 表单相关辅助方法2.1 Html.BeginForm() …...

uniapp 开发ios, xcode 提交app store connect 和 testflight内测

uniapp 中配置 配置manifest 文档&#xff1a;manifest.json 应用配置 | uni-app官网 hbuilderx中本地打包 下载IOS最新SDK 开发环境 | uni小程序SDK hbulderx 版本号&#xff1a;4.66 对应的sdk版本 4.66 两者必须一致 本地打包的资源导入到SDK 导入资源 | uni小程序SDK …...

人工智能--安全大模型训练计划:基于Fine-tuning + LLM Agent

安全大模型训练计划&#xff1a;基于Fine-tuning LLM Agent 1. 构建高质量安全数据集 目标&#xff1a;为安全大模型创建高质量、去偏、符合伦理的训练数据集&#xff0c;涵盖安全相关任务&#xff08;如有害内容检测、隐私保护、道德推理等&#xff09;。 1.1 数据收集 描…...