网站建设与维护,网络公司是做什么的,郑州做企业网站哪家好,有限公司破产无力偿还债务怎么办第五十章 动态规划——数位DP模型一、什么是数位DP数位DP的识别数位DP的思路二、例题1、AcWing 1083. Windy数#xff08;数位DP#xff09;2、AcWing 1082. 数字游戏#xff08;数位DP#xff09;3、AcWing 1081. 度的数量#xff08;数位DP#xff09;一、什么是数位DP…
第五十章 动态规划——数位DP模型一、什么是数位DP数位DP的识别数位DP的思路二、例题1、AcWing 1083. Windy数数位DP2、AcWing 1082. 数字游戏数位DP3、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
