💧 dp 就 dp ,数位dp是什么意思 ?💧
🌷 仰望天空,妳我亦是行人.✨
🦄 个人主页——微风撞见云的博客🎐
🐳 数据结构与算法专栏的文章图文并茂🦕生动形象🦖简单易学!欢迎大家来踩踩~🌺
🪁 希望本文能够给读者带来一定的帮助🌸文章粗浅,敬请批评指正!🐥
🌊数位dp的概念
💧数位dp的概念:是一种计数用的dp,通常是统计一个区间[l,r]内满足一些条件数的个数。
💧数位的含义:一个数有个位、十位、百位、千位…数的每一位就即数位。
💧数位dp的本质:数位dp的本质就是以另一种形式的暴力枚举,同时这种枚举方式满足dp的性质,通常采用dfs+dp进行记忆化搜索。
的算法。
问题提要
我们以一道蓝桥杯2021年的国赛题目:二进制问题 来讲解:
🍊题目是这样的: 小 蓝 \color{#00BFFF}{小蓝} 小蓝最近在学习二进制。他想知道 1到N 中有多少个数满足其二进制表示中恰好有 K 个 1。你能帮助他吗?(1 ≤ N ≤ 10^18, 1 ≤ K ≤ 50)
思路分析
可以看到,给出的数据特别大
,直接暴力肯定超时。其实这是一道经典数位DP问题
,询问[1,N]中满足二进制有K个1的数字数目。数位dp解决的就是从某个区间中,求出满足特殊要求的数字数目
。那我们应该怎样去做呢?
如何求解
🍊在介绍数位dp之前,我们要先了解一个数位字典序
的概念:
💧我们把数字大小
— 转换为 —> 数位字典序
的大小
例如区间[1,12345],将长度小于5的数字补全前导0
,1→00001 , 123 →00123小于12345的数字,即等同于字典序小于12345
。
💧本题为二进制,则转换成二进制字典序枚举,100的二进制
表示形式是1100100,转换为字典序即: [0,100]=>[0000000,1100100]
这样的话,题目中问我们二进制中一共有多少个K是不是就简单了?我们只需要去枚举每一位
。
💧对于每一位,我们只需要确定它当前的取值范围是多少
即可。那取值范围
又是由什么因素决定的呢?我们很容易想到,在二进制中,如果高位是1的位置我给它取零的话,那他后面无论怎么取
,就算全取1,也不会比它原来的值大
。
💧而我们刚才提到的“取1” or “取0”,其实就是在判断当前位的上限和之前位的上限
,仔细想想看是否如此?
💧例如一个数为1000,假如把最高位变成0,那么0111也一定没有1000大
,对于二进制而言,我们最大所能取到的数就是1,十进制最大能取的数是9,由于题目是二进制,所以我们这里的上限就是1
。
🥏这里用dfs进行求解:
从最高位到最低位
按位枚举,我们需要记录以下一些内容:
- 枚举当前是第几位
- 当前存在多少个1
- 当前这一位可以填的上限是多少
前面两个都好处理,第三个变量“上限是多少”,这个我们如何来维护呢?
当前这一位可以填的上限是多少?[0,100] =>[0000000,1100100]
对于第3位:如果前两位填了1,则第3位上限只能是0。
如果前两位没有达到上限
,那么第3位就是二进制的取值范围[0,1]
为了维护这些状态,我们需要一个变量来记录前面所有数字是否达到上限!如果达到上限,那当前位就只能取原来数中该位的值,否则可以取该进制下最大的值。
代码实现
🎋slove()
这个方法主要是将数字转换成数位的字典序来存储
,这里直接右移
即可。然后枚举从高位开始
以dfs搜索的方式进行枚举。
long solve(long n) {
int len = 0;
while (n != 0) {//将数字的二进制存储在num里面(默认二进制右边是第一位)
num[++len] = (int) (n & 1);
n >>= 1;
}
return dfs(len, 0, true);
}
🎋dfs():
我们定义一个函数叫dfs(int len, int sum, boolean limit)
每个参数的含义分别是:
- len :当前是第几位
- sum :当前共有多少个1
- limit :当前是否达到上限
static long dfs(int len, int sum, boolean limit) {
if (len == 0) return sum == K ? 1 : 0;//递归出口
//计算当前位的上限
int up = limit ? num[len] : 1;//达到上限了吗?达到了就只能原样输出:否则就可以取二进制的最大值1.(这道题是二进制)
long res = 0;
for (long i = 0; i <= up; i++) {//对当前位能取到的情况进行暴力枚举,统计答案
//第三个表达式:limit && i == up 的意思是:(注意短路与&&)
//1.如果limit没有达到上限(false),那整个表达式永远不会达到上限,return false,下一次可以随便取
//2.如果limit已经达到上限,那我还要判断一下当前位是否已经到了当前位的上限,
// 2.1如果i == up,那总体就算达到上限,返回true,带着这个状态继续往下走。
// 2.2如果i != up,就表明当前位上是没有达到上限的,所以总体来说也是没有达到上限的,可以带着false的状态继续深搜。
res += dfs(len - 1, sum + (i == 1 ? 1 : 0), limit && i == up);
}
return res;
}
仔细推敲一下,我们发现,这样的搜索方式存在很多重复枚举
:
当limit=False时,后续所有状态均为False,此时与原来的数字中的每个位无关,答案是相同的
,所以我们采用记忆化搜索
来达到一种剪枝
的目的!
新加两行代码,用于记忆化搜索(备忘录)
:
//当limit == false的时候,后续所有状态均为false,此时与num数组无关,答案是相同的,采用记忆化搜索
//记忆化搜索DFS:只要这个状态的limit为false,并且曾经访问过,直接返回DP数组记录的答案。(没有达到上限时,我们搜到相同地方的答案都是一样的)
if (dp[len][sum] != -1 && !limit) return dp[len][sum];//如果没有达到上限并且该处有记录就直接return掉
dp[len][sum] = res;//如果上一次达到上限,并且当前情况(len,sum)没有出现过记录,那么我们就在这里给它做记录
完整dfs代码如下:
long dfs(int len, int sum, boolean limit) {
if (len == 0) return sum == K ? 1 : 0;
if (dp[len][sum] != -1 && !limit) return dp[len][sum];
int up = limit ? num[len] : 1;
long res = 0;
for (long i = 0; i <= up; i++)
res += dfs(len - 1, sum + (i == 1 ? 1 : 0), limit && i == up);
dp[len][sum] = res;
return res;
}
🎏完整题解代码
import java.io.*;
import java.util.*;
/**
* @Auther: LiangXinRui
* @Date: 2023/3/24 11:33
* @Description: 数位DP
*/
public class Main {
static long n, K;
static long[][] dp = new long[66][66];//长度为len且1的个数为sum时的值(备忘录)
static int[] num = new int[66];//用数组来存储n的二进制
static StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
static PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
public static void main(String[] args) throws IOException {
n = nextLong();
K = nextLong();
out.println(solve(n));
out.flush();
}
/**
* @param len :当前是第几位
* @param sum :表示多少个1
* @param limit :表示是否达到上限
* @deprecated :这样写 : ~a != 0 就是说 a != -1
*/
static long dfs(int len, int sum, boolean limit) {
if (len == 0) return sum == K ? 1 : 0;//递归出口
//当limit == false的时候,后续所有状态均为false,此时与num数组无关,答案是相同的,采用记忆化搜索
//记忆化搜索DFS:只要这个状态的limit为false,并且曾经访问过,直接返回DP数组记录的答案。(没有达到上限时,我们搜到相同地方的答案都是一样的)
if (dp[len][sum] != -1 && !limit) return dp[len][sum];//如果没有达到上限并且该处有记录就直接return掉
//计算当前位的上限
int up = limit ? num[len] : 1;//达到上限了吗?达到了就只能原样输出:否则就可以取二进制的最大值1.(这道题是二进制)
long res = 0;
for (long i = 0; i <= up; i++) {//对当前位能取到的情况进行暴力枚举,统计答案
//第三个表达式:limit && i == up 的意思是:(注意短路与&&)
//1.如果limit没有达到上限(false),那整个表达式永远不会达到上限,return false,下一次可以随便取
//2.如果limit已经达到上限,那我还要判断一下当前位是否已经到了当前位的上限,
// 2.1如果i == up,那总体就算达到上限,返回true,带着这个状态继续往下走。
// 2.2如果i != up,就表明当前位上是没有达到上限的,所以总体来说也是没有达到上限的,可以带着false的状态继续深搜。
res += dfs(len - 1, sum + (i == 1 ? 1 : 0), limit && i == up);
}
dp[len][sum] = res;//如果上一次达到上限,并且当前情况(len,sum)没有出现过记录,那么我们就在这里给它做记录
return res;
}
static long solve(long n) {
for (long[] longs : dp) Arrays.fill(longs, -1);//初始化dp
int len = 0;
while (n != 0) {//将数字的二进制存储在num里面(默认二进制右边是第一位)
num[++len] = (int) (n & 1);
n >>= 1;
}
return dfs(len, 0, true);
}
static long nextLong() throws IOException {
in.nextToken();
return (long) in.nval;
}
}
🌊巩固加深
题目:不要62
大致意思&&思路:
数位上不能有4也不能有连续的62,没有4的话在枚举的时候判断一下,不枚举4就可以保证状态合法了,
所以这个约束没有记忆化的必要,而对于62的话,涉及到两位,当前一位是6或者不是6这两种不同情况我计数是不相同的,所以要用状态来记录不同的方案数。
dp[pos][sta]表示当前第pos位,前一位是否是6的状态,这里sta只需要去0和1两种状态就可以了,不是6的情况可视为同种,不会影响计数。
输入1 100
输出80
import java.util.Arrays;
import java.util.Scanner;
public class Main {
static int left, right;
//dp[pos][sta]表示当前第pos位,前一位是否是6的状态,这里sta只需要去0和1两种状态就可以了,不是6的情况可视为同种,不会影响计数。
static int[][] dp = new int[20][2];
static int[] a = new int[20];
static long dfs(int pos, int pre, int sta, boolean limit) {
if (pos == -1) return 1;
if (!limit && dp[pos][sta] != -1) return dp[pos][sta];
int up = limit ? a[pos] : 9;
int temp = 0;
for (int i = 0; i <= up; i++) {
if (pre == 6 && i == 2) continue;
if (i == 4) continue;
temp += dfs(pos - 1, i, i == 6 ? 1 : 0, limit && i == a[pos]);
}
if (!limit) dp[pos][sta] = temp;
return temp;
}
static long solve(int x) {
int pos = 0;
while (x != 0) {
a[pos++] = x % 10;
x /= 10;
}
return dfs(pos - 1, -1, 0, true);
}
public static void main(String[] args) {
Scanner cin = new Scanner(System.in);
left = cin.nextInt();
right = cin.nextInt();
for (int[] ints : dp) Arrays.fill(ints, -1);
System.out.println(solve(right) - solve(left - 1));
}
}
🐳结语
🐬初学一门技术时,总有些许的疑惑,别怕,它们是我们学习路上的点点繁星,帮助我们不断成长。
🐟文章粗浅,希望对大家有帮助!文章来源:https://www.toymoban.com/news/detail-414831.html
🦄参考:数位dp总结 之 从入门到模板 、蓝桥云课文章来源地址https://www.toymoban.com/news/detail-414831.html
到了这里,关于dp 就 dp ,数位dp是什么意思 ?的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!