第五十章 动态规划——数位DP模型
第五十章 动态规划——数位DP模型
- 一、什么是数位DP
- 数位DP的识别
- 数位DP的思路
- 二、例题
- 1、AcWing 1083. Windy数（数位DP）
- 2、AcWing 1082. 数字游戏（数位DP）
- 3、AcWing 1081. 度的数量（数位DP）
一、什么是数位DP
数位DP的识别
当一道题问我们，数轴上，某个区间内的数，满足某个条件的个数。
一般像这种题我们会使用数位DP的逻辑。
数位DP的思路
数位DP顾名思义就是按照数字的每一位去讨论。
那么数位DP做题思路分为两步：按位枚举，分类讨论
我们把区间的上限X写出来：
那么怎么分类讨论呢？
从上到下是从高位到低位枚举的，对于每一位我们的分类依据是：(0 ~ a - 1)和a，那么为什么这么分呢？
一般数位DP都是让我们挑选满足某个条件的数，我们不仅需要考虑某个数是否满足条件，还需要考虑某个数是否小于上限值。
那么我们在分类讨论以后，就发现我们分出的第一类情况中：0~a-1，由于高位都小于了a，那么这个数肯定比上限X小，也就是说此时我们只需要考虑是否满足题目中的某个条件。
我们对每一位都做这样的操作，只不过越往下分，每个数字固定的前缀就越长，最后我们会发现所有二叉树的右儿子恰好组成了我们上限值。
那么有人可能会想，题目中问的有可能是个区间，难道我们不需要考虑这个数必须大于等于下限吗？
这里可以使用一个思路，假设f[n]f[n]f[n]是满足所有小于等于上限值的数的数量，我们只需要再减去小于下限m的数目，即f[m−1]f[m - 1]f[m−1]的值，就是区间[n,m][n,m][n,m]内符合题目条件的数目。
我们发现上面介绍的仅仅是分类讨论，那和DP有什么关系呢？
其实当我们进行分类讨论后，我们发现左支部分枚举的数是不需要关注他的大小是否超过区间上限的，因此我们只需要考虑它是否满足某个条件，而找出符合该条件的数目的时候往往需要用DP。
二、例题
1、AcWing 1083. Windy数（数位DP）
这道题中要格外注意前导零的问题。
AcWing 1083. Windy数（数位DP）
2、AcWing 1082. 数字游戏（数位DP）
AcWing 1082. 数字游戏（数位DP）
3、AcWing 1081. 度的数量（数位DP）
AcWing 1081. 度的数量（数位DP）
相关文章：
第五十章 动态规划——数位DP模型
第五十章 动态规划——数位DP模型一、什么是数位DP数位DP的识别数位DP的思路二、例题1、AcWing 1083. Windy数（数位DP）2、AcWing 1082. 数字游戏（数位DP）3、AcWing 1081. 度的数量（数位DP）一、什么是数位DP…...
02- pandas 数据库 (机器学习)
pandas 数据库重点: pandas 的主要数据结构: Series (一维数据)与 DataFrame (二维数据)。 pd.DataFrame(data np.random.randint(0,151,size (5,3)), # 生成pandas数据 index [Danial,Brandon,softpo,Ella,Cindy], # 行索引 …...
学Qt想系统的学习，看哪本书?
Qt 是一个跨平台应用开发框架（framework），它是用 C语言写的一套类库。使用 Qt 能为 桌面计算机、服务器、移动设备甚至单片机开发各种应用（application），特别是图形用户界面 （graphical user in…...
2023年网络安全比赛--跨站脚本攻击②中职组（超详细）
一、竞赛时间 180分钟 共计3小时 二、竞赛阶段 1.访问服务器网站目录1，根据页面信息完成条件，将获取到弹框信息作为flag提交； 2.访问服务器网站目录2，根据页面信息完成条件，将获取到弹框信息作为flag提交； 3.访问服务器网站目录3，根据页面信息完成条件，将获取到弹框信息…...
网络安全实验室4.注入关
4.注入关 1.最简单的SQL注入 url:http://lab1.xseclab.com/sqli2_3265b4852c13383560327d1c31550b60/index.php 查看源代码，登录名为admin 最简单的SQL注入，登录名写入一个常规的注入语句： admin’ or ‘1’1 密码随便填，验证…...
领域搜索算法之经典The Lin-Kernighan algorithm
领域搜索算法之经典The Lin-Kernighan algorithmThe Lin-Kernighan algorithm关于算法性能提升的约束参考文献领域搜索算法是TSP问题中的三大经典搜索算法之一，另外两种分别是回路构造算法和组合算法。 而这篇文章要介绍的The Lin-Kernighan algorithm属于领域搜索算…...
深度学习基础-机器学习基本原理
本文大部分内容参考《深度学习》书籍，从中抽取重要的知识点，并对部分概念和原理加以自己的总结，适合当作原书的补充资料阅读，也可当作快速阅览机器学习原理基础知识的参考资料。 前言 深度学习是机器学习的一个特定分支。我们要想…...
C语言操作符详解 一针见血！
目录算数操作符移位操作符位操作符赋值操作符单目操作符关系操作符逻辑操作符条件操作符逗号表达式下标引用、函数调用和结构成员表达式求值11.1 隐式类型转换算数操作符💭 注意/ 除法 --得到的是商% 取模（取余）--得到的是余数如果除法操作符…...
前端面试题汇总
一：JavaScript 1、闭包是什么？利弊？如何解决弊端？ 闭包是什么：JS中内层函数可以访问外层函数的变量，外层函数无法操作内存函数的变量的特性。我们把这个特性称作闭包。 闭包的好处： 隔离作用…...
以数据驱动管理场景，低代码助力转型下一站
数据驱动 数据驱动，是通过移动互联网或者其他的相关软件为手段采集海量的数据，将数据进行组织形成信息，之后对相关的信息讲行整合和提炼，在数据的基础上经过训练和拟合形成自动化的决策模型，简单来说，就是…...
2023年全国数据治理DAMA-CDGA/CDGP考试报名到弘博创新
弘博创新是DAMA中国授权的数据治理人才培养基地，贴合市场需求定制教学体系，采用行业资深名师授课，理论与实践案例相结合，快速全面提升个人/企业数据治理专业知识与实践经验，通过考试还能获得数据专业领域证书。 DAMA认…...
流程控制之循环
文章目录五、流程控制之循环5.1 步进循环语句for5.1.1 带列表的for循环语句5.1.2 不带列表的for循环语句5.1.3 类C风格的for循环语句5.2 while循环语句5.2.1 while循环读取文件5.2.2 while循环语句示例5.3 until循环语句5.4 select循环语句5.5 嵌套循环5.4 利用break和continue…...
SpringDataRedis快速入门
SpringDataRedis快速入门1.SpringDataRedis简介2.RedisTemplate快速入门3.RedisSerializer4.StringRedisTemplate1.SpringDataRedis简介 SpringData是Spring中数据操作的模块，包含对各种数据库的集成，其中对Redis的集成模块就叫做SpringDataRedis Spri…...
MySQL 的执行计划 explain 详解
目录 什么是执行计划 执行计划的内容 select子句的类型 访问类型 索引的存在形式...
2023年网络安全比赛--Web综合渗透测试中职组（超详细）
一、竞赛时间 180分钟 共计3小时 二、竞赛阶段 1.通过URL访问http://靶机IP/1，对该页面进行渗透测试,将完成后返回的结果内容作为FLAG值提交； 2.通过URL访问http://靶机IP/2，对该页面进行渗透测试,将完成后返回的结果内容作为FLAG值提交； 3.通过URL访问http://靶机IP/3，对…...
【c++之于c的优化 - 下】
前言 一、inline 概念 以inline修饰的函数叫做内联函数，编译时C编译器会在调用内联函数的地方展开，没有函数调用建立栈帧的开销，内联函数提升程序运行的效率。 如果在上述函数前增加inline关键字将其改成内联函数，在编译期间编译…...
MySQL事务管理
文章目录MySQL事务管理事务的概念事务的版本支持事务的提交方式事务的相关演示事务的隔离级别查看与设置隔离级别读未提交（Read Uncommitted）读提交（Read Committed）可重复读（Repeatable Read）串行化&#…...
二维计算几何全家桶
参考文章：范神的神仙博客 前置芝士 一些高中数学 向量的叉积：向量的点积为 a⋅b∣a∣∣b∣cos<a,b>a\cdot b|a||b|\cos<a,b>a⋅b∣a∣∣b∣cos<a,b>，向量的叉积为 ab∣a∣∣b∣sin<a,b>a\times b|a||b|\sin<…...
基于图的下一代入侵检测系统
青藤云安全是一家主机安全独角兽公司，看名字就知道当前很大一块方向专注云原生应用安全，目前主营的是主机万相/容器蜂巢产品，行业领先，累计支持 800万 Agent。当前公司基于 NebulaGraph 结合图技术开发的下一代实时入侵检测系统已…...
若依框架---树状层级部门数据库表
👏作者简介：大家好，我是小童，Java开发工程师，CSDN博客博主，Java领域新星创作者 📕系列专栏：前端、Java、Java中间件大全、微信小程序、微信支付、若依框架、Spring全家桶 Ǵ…...
Python爬虫实战：研究MechanicalSoup库相关技术
一、MechanicalSoup 库概述 1.1 库简介 MechanicalSoup 是一个 Python 库，专为自动化交互网站而设计。它结合了 requests 的 HTTP 请求能力和 BeautifulSoup 的 HTML 解析能力，提供了直观的 API，让我们可以像人类用户一样浏览网页、填写表单和提交请求。 1.2 主要功能特点…...
【HarmonyOS 5.0】DevEco Testing：鸿蒙应用质量保障的终极武器
——全方位测试解决方案与代码实战 一、工具定位与核心能力 DevEco Testing是HarmonyOS官方推出的一体化测试平台，覆盖应用全生命周期测试需求，主要提供五大核心能力： 测试类型检测目标关键指标功能体验基…...
STM32+rt-thread判断是否联网
一、根据NETDEV_FLAG_INTERNET_UP位判断 static bool is_conncected(void) {struct netdev *dev RT_NULL;dev netdev_get_first_by_flags(NETDEV_FLAG_INTERNET_UP);if (dev RT_NULL){printf("wait netdev internet up...");return false;}else{printf("loc…...
【C语言练习】080. 使用C语言实现简单的数据库操作
080. 使用C语言实现简单的数据库操作 080. 使用C语言实现简单的数据库操作使用原生APIODBC接口第三方库ORM框架文件模拟1. 安装SQLite2. 示例代码：使用SQLite创建数据库、表和插入数据3. 编译和运行4. 示例运行输出：5. 注意事项6. 总结080. 使用C语言实现简单的数据库操作 在…...
Redis数据倾斜问题解决
Redis 数据倾斜问题解析与解决方案 什么是 Redis 数据倾斜 Redis 数据倾斜指的是在 Redis 集群中，部分节点存储的数据量或访问量远高于其他节点，导致这些节点负载过高，影响整体性能。 数据倾斜的主要表现 部分节点内存使用率远高于其他节…...
稳定币的深度剖析与展望
一、引言 在当今数字化浪潮席卷全球的时代，加密货币作为一种新兴的金融现象，正以前所未有的速度改变着我们对传统货币和金融体系的认知。然而，加密货币市场的高度波动性却成为了其广泛应用和普及的一大障碍。在这样的背景下，稳定…...
力扣-35.搜索插入位置
题目描述 给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。 请必须使用时间复杂度为 O(log n) 的算法。 class Solution {public int searchInsert(int[] nums, …...
让回归模型不再被异常值“带跑偏“，MSE和Cauchy损失函数在噪声数据环境下的实战对比
在机器学习的回归分析中，损失函数的选择对模型性能具有决定性影响。均方误差（MSE）作为经典的损失函数，在处理干净数据时表现优异，但在面对包含异常值的噪声数据时，其对大误差的二次惩罚机制往往导致模型参数…...
QT3D学习笔记——圆台、圆锥
类名作用Qt3DWindow3D渲染窗口容器QEntity场景中的实体（对象或容器）QCamera控制观察视角QPointLight点光源QConeMesh圆锥几何网格QTransform控制实体的位置/旋转/缩放QPhongMaterialPhong光照材质（定义颜色、反光等）QFirstPersonC…...
人工智能（大型语言模型 LLMs）对不同学科的影响以及由此产生的新学习方式
今天是关于AI如何在教学中增强学生的学习体验，我把重要信息标红了。人文学科的价值被低估了 ⬇️ 转型与必要性 人工智能正在深刻地改变教育，这并非炒作，而是已经发生的巨大变革。教育机构和教育者不能忽视它，试图简单地禁止学生使…...