数位dp笔记

数位dp:
一、问题简介:

与数位有关的区间统计问题

例:求给定区间中,满足给定条件的某个D进制数的数量,而限定条件往往与数位有关,比如数位之和,制定数码个数,数的大小分组等

基本思想:逐位确定,预处理

二、通用状态:

1.预处理,从高位到低位枚举当前数字第一次小于n的那一位,这样的话,之前的位数都已经确定(都与n相等),之后的位数可以随意枚举。

2.f[i][j]表示处理到第i位,这i位的状态是j时的数字个数

或者:f[i][j][n][m]表示处理到第i位,这i位的状态是j,限制是nm时的数字个数

三、自己的summary:

1.数位dp是在没有限制的条件下进行预处理的,所以在我们实际循环中应该判断这一位到第有没有限制,分情况进行更新

2.注意循环顺序,一般而言都是从高位到低位

----------------持续更新?----------------✿✿ヽ(°▽°)ノ✿-----------------

原文地址:https://www.cnblogs.com/yxr001002/p/14436424.html