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

dp 就 dp ，数位dp是什么意思？

news 来源：原创 2024/4/25 8:01:54

在这里插入图片描述

💧 dp 就 dp ，数位dp是什么意思？💧

🌷 仰望天空，妳我亦是行人.✨
🦄 个人主页——微风撞见云的博客🎐
🐳 数据结构与算法专栏的文章图文并茂🦕生动形象🦖简单易学！欢迎大家来踩踩~🌺
🪁 希望本文能够给读者带来一定的帮助🌸文章粗浅，敬请批评指正！🐥

文章目录

🌊数位dp的概念
- 问题提要
- 思路分析
- 如何求解
- 代码实现
- - 🎋slove()
  - 🎋dfs()：
- 🎏完整题解代码
🌊巩固加深
🐳结语

🌊数位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);//初始化dpint 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));}
}

在这里插入图片描述

🐳结语

🐬初学一门技术时，总有些许的疑惑，别怕，它们是我们学习路上的点点繁星，帮助我们不断成长。

🐟文章粗浅，希望对大家有帮助！

🦄参考：数位dp总结之从入门到模板、蓝桥云课

文章目录

🌊数位dp的概念

问题提要

思路分析

如何求解

代码实现

🎋slove()

🎋dfs()：

🎏完整题解代码

🌊巩固加深

🐳结语

相关文章：