dp 就 dp ,数位dp是什么意思 ?

这篇具有很好参考价值的文章主要介绍了dp 就 dp ,数位dp是什么意思 ?。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

dp 就 dp ,数位dp是什么意思 ?

                                                                  💧 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;
    }
}

dp 就 dp ,数位dp是什么意思 ?

🌊巩固加深

题目:不要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 ,数位dp是什么意思 ?


🐳结语

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

🐟文章粗浅,希望对大家有帮助!

🦄参考:数位dp总结 之 从入门到模板 、蓝桥云课文章来源地址https://www.toymoban.com/news/detail-414831.html

到了这里,关于dp 就 dp ,数位dp是什么意思 ?的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 动态规划——数位DP 学习笔记

    引入 数位 DP 往往都是这样的题型:给定一个区间 ([l, r]) ,求这个区间中满足某种条件的数的总数。 简单的暴力代码如下: 而当数据规模过大,暴力枚举就 (mathbb T) 飞了,因此引入数位 DP: 概念 数位(digit):对于十进制,即把一个数字按照个位、十位、百位等,一位

    2024年02月08日
    浏览(47)
  • LeetCode---121双周赛---数位dp

    2996. 大于等于顺序前缀和的最小缺失整数 2997. 使数组异或和等于 K 的最少操作次数 2998. 使 X 和 Y 相等的最少操作次数 2999. 统计强大整数的数目 简单的模拟题,只要按照题目的要求去写代码即可,代码如下 这题考异或的性质---相同为0,相异为1,我们只要关心nums的异或和与

    2024年01月22日
    浏览(56)
  • 异或三角形(数位dp)

    [Link](异或三角 - 蓝桥云课 (lanqiao.cn)) 参考:2021蓝桥杯国赛-J异或三角形-数位dp_塔子哥来了的博客-CSDN博客_蓝桥杯数位dp 给定 T T T 个数 n 1 , n 2 , . . . , n T n_1,n_2,...,n_T n 1 ​ , n 2 ​ , . . . , n T ​ ,对每个 n i n_i n i ​ 请求出有多少组 a , b , c a,b,c a , b , c 满足: 1 ≤ a , b , c ≤

    2024年02月09日
    浏览(42)
  • 周赛348(模拟、反向思维、数位DP)

    难度中等3 给你一个下标从 0 开始的字符串 s ,重复执行下述操作 任意 次: 在字符串中选出一个下标 i ,并使 c 为字符串下标 i 处的字符。并在 i 左侧 (如果有)和 右侧 (如果有)各 删除 一个距离 i 最近 的字符 c 。 请你通过执行上述操作任意次,使 s 的长度 最小化 。

    2024年02月07日
    浏览(74)
  • C++ 动态规划 数位统计DP 计数问题

    给定两个整数 a 和 b ,求 a 和 b 之间的所有数字中 0∼9 的出现次数。 例如,a=1024,b=1032 ,则 a 和 b 之间共有 9 个数如下: 1024 1025 1026 1027 1028 1029 1030 1031 1032 其中 0 出现 10 次,1 出现 10 次,2 出现 7 次,3 出现 3 次等等… 输入格式 输入包含多组测试数据。 每组测试数据占一

    2024年02月20日
    浏览(42)
  • 「数位dp」统计整数数目(力扣第2719题)

    本题为1月16日力扣每日一题 题目来源:力扣第2719题 题目tag: 数位dp 动态规划 给你两个数字字符串num1和num2,以及两个整数max_sum和min_sum。如果一个整数x满足以下条件,我们称它是一个好整数: (num1 leq x leq num2) (min_sum leq digit_sum(x) leq max_sum) 请你返回好整数的数目。答案

    2024年01月16日
    浏览(40)
  • 算法竞赛备赛进阶之数位DP训练

    数位DP的思想就是对每一位进行DP,计算时记忆化每一位可以有的状态,其作用是减少运算时间,避免重复计算。 数位DP是一种计数用的DP,一般就是要统计一个区间[A,B]内满足一些条件数的个数。 以1e9甚至1e18、1e100的问题为例,因为在统计情况下有很多重复的计算,数位DP实

    2024年01月16日
    浏览(49)
  • LeetCode 2719. 统计整数数目,数位dp板子题

    1、题目描述 给你两个数字字符串  num1  和  num2  ,以及两个整数  max_sum  和  min_sum  。如果一个整数  x  满足以下条件,我们称它是一个好整数: num1 = x = num2 min_sum = digit_sum(x) = max_sum . 请你返回好整数的数目。答案可能很大,请返回答案对  109 + 7  取余后的结果。 注意

    2024年01月17日
    浏览(43)
  • acwing算法基础之动态规划--数位统计DP、状态压缩DP、树形DP和记忆化搜索

    暂无。。。 暂无。。。 题目1 :求a~b中数字0、数字1、…、数字9出现的次数。 思路:先计算1~a中每位数字出现的次数,然后计算1~b-1中每位数字出现的次数,两个相减即是最终答案。 那么,如何计算1~a中每位数字出现的次数呢? 首先,将a的每一位存入向量num中,例如a=123

    2024年02月04日
    浏览(51)
  • 【动态规划】【 数位dp】2827. 范围中美丽整数的数目

    数位dp 动态规划汇总 给你正整数 low ,high 和 k 。 如果一个数满足以下两个条件,那么它是 美丽的 : 偶数数位的数目与奇数数位的数目相同。 这个整数可以被 k 整除。 请你返回范围 [low, high] 中美丽整数的数目。 示例 1: 输入:low = 10, high = 20, k = 3 输出:2 解释:给定范围

    2024年04月12日
    浏览(42)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包