数位DP算法学习总结

article/2024/6/24 19:12:34

一、数位dp简述+模板

数位dp是一种计数时使用的动态规划算法,一般是要统计一个区间 [left, right] 内符合给定条件数字的个数,例如HDU 2089 不要62中的统计给定区间内不包含4以及62数字的个数,数位dp其实是暴力枚举算法的优化,通过过滤一些数字,以及记忆化(以下会讲)一些数据,达到优化时间复杂度。

首先 dfs(int step, int state, bool lead, bool limit) 函数有四个参数

  • step:表示当前枚举到第几位数,例如1-100,先枚举百位数的数字,再枚举十位数的数字,最后枚举个位数的数字

  • state:状态条件,用于记忆化,比如我们要统计[1,9299]之间不含4数字的个数,按理说我们先应该先从1开始枚举,当枚举到1000的时候,此时我们已经知道到了当只有三位数时,不含4数字的个数,那么当我们在枚举千位的数字时,当千位数字为1时,我们已经知道了其后三位数不含4数字的个数,当千位数字来到2时,我们可以直接返回结果,因为千位数1和2均不含4,那么千位数1和千位数2后面三位数中不论怎么搭配,不含数字4的个数一定是一样的,如此可以记忆化数组,避免重复性的计算。

  • lead:前导零,某些问题中前导零如00xxx的情况也会影响结果,所以要设置一个bool变量lead,当然,在某些问题下,前导零并不影响结果,所以可以不使用它

  • limit:限制标记,我们要枚举所有数字,这些数字一定是有上界的,例如上述我们要枚举[1,9299]之间的数据,当千位数为9时,显然百位数最高只能枚举到2,否则就超出了枚举的上界,但当千位数为8时,此时没有上界可言,因为千位数为8,不论其后三位数是什么都不会超出9299的范围

其次,solve(int x) 的作用是取出一个数的各个位数,用于dfs的遍历

以下是数位dp的模板:

#include<iostream>
using namespace std;
int a[20]; //存储数字位数
int dp[20][2]; //记忆化数组int dfs(int step, int state, bool lead, bool limit) {if (step == -1) return 1; //当遍历到超出数字位数时,说明此情况可行,返回1if (!limit && !lead && dp[step][state] != -1) //记忆化,节省重复计算return dp[step][state];int up = limit ? v[step] : 9;  //取得上界int ans = 0; //开始计数for (int i = 0; i <= up; i++) {if (条件1) ...if (条件2) ...ans += dfs(step + 1, /*状态转移*/, lead && i == 0, limit && i == v[step]);}if (!limit && !lead) //在一定条件下记录结果,对应上面记忆化dp[step][state] = ans;return ans;
}
int solve(int x) {int pos = 0;while (x) { //取出各个位的数字,存在a中a[pos++] = x % 10;x /= 10;}memset(dp, -1, sizeof(dp)); //初始化dp数组值为-1return dfs(pos - 1, /*状态*/, true, true); //刚开始比最高位还高的数字为0,所以有前导零,并且有限制
}
int main() {int le, ri;while (cin >> le >> ri) {int ans = solve(ri) - solve(le - 1);cout << ans << endl;}return 0;
}

二、HDU 2089 不要62 数位dp题解

state变量应用限制条件最强的来记忆化,例如此题不存在62限制为两位,不存在4限制只有一位,所以state标记为此位是否为6,假设求解[1,100]中符合条件的个数,如果state表示为is_four,那么十位为5和十位为6其后个位数符合条件的数字是一样的,因为5和6都不是4,但当十位为6时,个位就不能为2(这是题目要求的),所以就造成了数据不一致的情况,以此得出state变量应用限制条件最强的来进行记忆化。

#include<iostream>
#include<vector>
using namespace std;
int a[20];
int dp[20][2];int dfs(int step, int pre, bool is_six, bool limit) { //pre为前一位数字,用于判断是否存在62,此处is_six就是模板中的state,表示当此位为6和不为6时,后续的结果不同if (step == -1) return 1;if (!limit && dp[step][is_six] != -1) return dp[step][is_six];int up = limit ? a[step] : 9;int ans = 0;for (int i = 0; i <= up; i++){if (i == 4) continue; //存在4则跳过if (i == 2 && pre == 6) continue; //存在62则跳过ans += dfs(step - 1, i, i == 6, limit && i == a[step]);}if (!limit) dp[step][is_six] = ans;return ans;
}
int solve(int x) {int pos = 0;while (x != 0) {a[pos++] = x % 10;x /= 10;}memset(dp, -1, sizeof(dp)); //初始化dp数组值为-1return dfs(pos - 1, -1, 0, true);
}
int main() {int n, m;while (cin >> n >> m && n != 0 && m != 0) {int ans = solve(m) - solve(n - 1);cout << ans << endl;}return 0;
}

http://www.ngui.cc/article/show-1007678.html

相关文章

添加Anaconda Powershell Prompt到右键

想要使用Anaconda Powershell Prompt每次还要去开始菜单打开&#xff0c;而且还要切换到特定目录下&#xff0c;十分麻烦。通过将Anaconda Powershell Prompt添加到鼠标右键&#xff0c;可在当前目录十分方便的打开Anaconda Powershell Prompt。步骤如下&#xff1a; 1. 首先开…

Java_Spring:4. 使用 spring 的 IoC 的实现CRUD【案例】

目录 1 需求和技术要求 1.1 需求 1.2 技术要求 2 环境搭建 2.1 拷贝 jar 包 2.2 创建数据库和编写实体类 2.3 编写持久层代码 2.4 编写业务层代码 2.5 创建并编写配置文件 3 配置步骤 4 测试案例 4.1 测试类代码 4.2 分析测试了中的问题 1 需求和技术要求 1.1 需求…

Spring - Spring 注解相关面试题总结

文章目录01. Spring 配置方式有几种&#xff1f;02. Spring 如何实现基于xml的配置方式&#xff1f;03. Spring 如何实现基于注解的配置&#xff1f;04. Spring 如何基于注解配置bean的作用范围&#xff1f;05. Spring Component, Controller, Repository, Service 注解有何区别…

2023-3-25 java选择题每日一练

继承中类, 静态代码块, 实例代码块和构造方法的执行顺序其原理如下:当没有子类继承的时候顺序&#xff1a;静态代码块 → main → 构造代码块 → 构造方法public class Test {static{System.out.println("父类静态代码块开始执行&#xff01;");}{System.out.println…

【WMS学习】从悬浮窗的添加来看窗口的add和update

这里我们从一个悬浮窗应用来查看WindowManager的addView使用&#xff0c;从这里作为突破口来认识窗口的添加&#xff0c;和窗口的位置大小更新方法updateViewLayout&#xff0c;使用WindowManager的addView方法来添加窗口非常的直观&#xff0c;因为Activity的显示中&#xff0…

领域驱动设计(Domain-Driven Design, DDD)

领域驱动设计&#xff08;Domain Driven Design&#xff0c;简称DDD&#xff09;是一种面向对象软件开发方法&#xff0c;它强调将软件系统的设计和实现过程与业务领域紧密结合&#xff0c;通过深入理解和建模业务领域&#xff0c;从而达到高内聚、低耦合的目的。 领域驱动设计…

【ChatGPT】比尔·盖茨最新分享:ChatGPT的发展,不止于此

✅作者简介&#xff1a;在读博士&#xff0c;伪程序媛&#xff0c;人工智能领域学习者&#xff0c;深耕机器学习&#xff0c;交叉学科实践者&#xff0c;周更前沿文章解读&#xff0c;提供科研小工具&#xff0c;分享科研经验&#xff0c;欢迎交流&#xff01;&#x1f4cc;个人…

【学习总结】IMU噪声的连续形式与离散形式

乱七八糟的&#xff0c;查了半天资料&#xff0c;整理如下。 &#xff08;网上其他地方的资料也很混乱&#xff0c;这篇总结是我综合比对&#xff0c;得出的结论&#xff09; 统一符号 连续形式&#xff1a; gyroscope white noise: σg\sigma_gσg​ accelerator white nois…

[puzzle-5]目标图形中拼图块能够存放的位置

有如下的八种拼图块,每块都是由八块小正方块构成, 这些拼图块刚好可以某种方式拼合放入给定的目标形状, 请以C或C++编程,自动求解 一种拼图方式 目标拼图: 从拼图块和目标图形中我们可以发现目标图形是8*8=64个方块,也就是目标图形需要使用上述8中拼图进行拼接,每个使…

CentOS挂载U盘拷贝文件

1.登录linux操作系统&#xff0c;将U盘插入主机 2.新建一个目录将U盘挂载到该目录 使用命令: mkdir /mnt/usb 3.查看可用的挂载点 使用命令&#xff1a; fdisk -l 4. 将U盘挂载到刚才建立的目录下 使用命令: mount /dev/sdb4 /mnt/usb 5.查看U盘识别情况 使用命令 &#x…