title: “数位dp模板”
date: 2024-06-03 10:42:02
updated: 2025-07-19 17:11:44
tag: [“notion”, “Algorithm”, “动态规划”]
categories: “Algorithm”
mathjax: true
comments: true
description: ‘
// leetcode 2376. 统计特殊整数
//大范围内每一位都不同的数字个数
/*
dp[p][mask][limit][zero]
代表着 “填充到了第p位(p从0开始)，已出现的数字集合为mask，limit为前i位是否为n的前缀，zero为前i位是否全部为0，
第i位及之后的位数可以任意构造但是最终构造的数小于等于n且各个位数各不相同” 的个数。
*/
string s;
int dp[10][1<<10][2][2];
int dfs(int p, int mask, int limit, int zero) {
if (p == s.size()) return 1-zero;//全是前导零则不算答案。
if (dp[p][mask][limit][zero] != -1) return dp[p][mask][limit][zero]; //遇到计算过的状态直接返回
int res = 0;
// 累计前导零的方案数
// limit=1,由于之前是存在前导零，所以构造的位数必定小于n的位数，第p+1位最多能取到9;
// zero=1，之前是前导零，现在也是填充0，所以第p+1位的zero=1
if (zero == 1) res += dfs(p+1, mask, 0, 1);
// 累计非前导零的方案方案数
// 枚举的下限取决于zero。
// 当存在前导零，由于当前统计非前导零的方案数，所以只能从1开始
// 若不存在前导零，当前从0开始构造是可以满足最终构造的数<=n的
// 枚举上限取决于limit。
// 当limit存在说明p之前构造的数恰好是n的前缀，此时若超过n的第p位则不满足最终构造的数<=n。
// 当limit不存在说明前p位构造的数已经在字典序上小于n的前p位了，第p位即使取9，最终构造的数也不会大于n
for (int i=(zero?1:0); i<=(limit?s[p]-'0':9); i++) {// 不设置当前位为前导零，若之前为前导零则当前可从0开始，否则是1，若limit存在当前值超过s[p]必定大于n
if (mask>>i&1) continue; //前p个构造的数中已经有i，跳过。
res += dfs(p+1, mask|1<<i, limit&&(i==s[p]-'0'), 0);
// limit = limit&&(i==s[p]-'0'), 当前p个数是n的前缀，且第p个数也取到了n的第p位则形成了长度为p+1的前缀
// zero = 0, 当前循环是统计非前导零的方案数。
}
return dp[p][mask][limit][zero] = res;
}
int countSpecialNumbers(int n) {
s = to_string(n);
memset(dp, -1, sizeof(dp));
return dfs(0, 0, 1, 1);
//limit=1，第一位的最大值最多不能超过s[0],否则大于n.
//zero=1，前导零存在后续的前导零才可以存在
}
template
using ll = long long;
namespace DDP {
string s;
int _base = 10;
ll dp[64][64][2][2];
ll dfs(int p, int rem, int limit, int zero) {
if (p == s.size()) return rem == 0;
auto& res = dp[p][rem][limit][zero];
if (res != -1) return res;
res = 0;
if (zero == 1) res += dfs(p+1, rem, 0, 1);
for (int i=(zero?1:0); i<=(limit?s[p]-'0':_base-1); i++) {
if (rem < i) continue;
res += dfs(p+1, rem-i, limit&&(i==s[p]-'0'), 0);
}
return res;
}
ll digitsDP(ll n, int rem, int base=10) { // 0到n中 base进制下数位和为rem 的个数
_base = base;
s = "";
while (n) {
s.push_back('0'+n%base);
n/=base;
}
reverse(s.begin(), s.end());
memset(dp, -1, sizeof(dp));
return dfs(0, rem, 1, 1);
}
};
数位dp类似题
class Solution {
public:
using ll = long long;
string s;
string sf;
ll lm;
ll dp[18][2][2];
ll dfs(int p, int limit, int zero) {
// cout << p << " " << limit << " " << zero << " " << endl;
if (p + sf.size() == s.size()) {
if (limit && stoll(s.substr(s.size()-sf.size())) < stoll(sf)) return 0;
return 1;
}
if (dp[p][limit][zero] != -1) return dp[p][limit][zero]; //遇到计算过的状态直接返回
ll res = 0;
if (zero == 1) {
res += dfs(p+1, 0, 1);
}
for (int i=(zero?1:0); i<=(limit?s[p]-'0':9); i++) {
if (i<=lm) {
res += dfs(p+1, limit&&(i==s[p]-'0'), 0);
}
}
return dp[p][limit][zero] = res;
}
ll cnt_pre(ll n) {
s = to_string(n);
if (stoll(sf) > n) return 0;
memset(dp, -1, sizeof(dp));
return dfs(0, 1, 1);
}
long long numberOfPowerfulInt(long long start, long long finish, int limit, string suf) {
sf = suf;
lm = limit;
ll a = cnt_pre(finish);
ll b = cnt_pre(start-1);
return a - b;
}
};
class Solution {
public:
const int MOD = 1e9+7;
string s;
int k;
int dp[1000][1000][2][2];
int opt(int x) {
if (x == 1) return 0;
int b = 0;
while (x) {
b += x&1;
x>>=1;
}
return opt(b)+1;
}
int dfs(int p, int c1, int limit, int zero) {
if (p == s.size()) {
if (zero) return 0;
return opt(c1)+1 <= k;
}
if (dp[p][c1][limit][zero] != -1) return dp[p][c1][limit][zero]; //遇到计算过的状态直接返回
int res = 0;
if (zero == 1) res += dfs(p+1, c1, 0, 1);
for (int i=(zero?1:0); i<=(limit?s[p]-'0':1); i++) {
res += dfs(p+1, c1+i, limit&&(i==s[p]-'0'), 0);
res %= MOD;
}
return dp[p][c1][limit][zero] = res;
}
int countKReducibleNumbers(string s, int k) {
this->s = s;
this->k = k;
memset(dp, -1, sizeof(dp));
return (dfs(0, 0, 1, 1) - (opt(count(s.begin(), s.end(), '1'))+1 <= k) + MOD)%MOD;
}
};
class Solution {
public:
using ll = long long;
string s;
int base = 10;
ll dp[64][64][2][2];
ll dfs(int p, int rem, int limit, int zero) {
if (p == s.size()) return rem == 0;
auto& res = dp[p][rem][limit][zero];
if (res != -1) return res;
res = 0;
if (zero == 1) res += dfs(p+1, rem, 0, 1);
for (int i=(zero?1:0); i<=(limit?s[p]-'0':1); i++) {
if (rem < i) continue;
res += dfs(p+1, rem-i, limit&&(i==s[p]-'0'), 0);
}
return res;
}
ll digitsDP(ll n, int rem, int base=10) {
this->base = base;
s = "";
while (n) {
s.push_back('0'+n%2);
n/=2;
}
reverse(s.begin(), s.end());
memset(dp, -1, sizeof(dp));
return dfs(0, rem, 1, 1);
}
long long popcountDepth(long long n, int k) {
if (k == 0) return 1;
if (k == 1) {
ll t = 2, res = 0;
while (t<=n) {
res++;
t<<=1;
}
return res;
}
long long ans = 0;
for (int i=2; i<=63; i++) {
auto pop_count = [](int x) {
int c = 0;
while (x) {
c += x%2;
x>>=1;
}
return c;
};
int cnt = 0;
for (int j=i; j!=1; j=pop_count(j)) cnt++;
if (cnt == k-1) {
ans += digitsDP(n,i,2);
}
}
return ans;
}
};
这是一种记忆化搜索的新思路——构造合法的前缀，维护后缀最优/计数值。
$f_{p,c,a}$含义为前p个数已经分割了c个组，且最后一组的与和为a，其可能构造的后缀中每个组的最后一个数的和
我们的目标就是求最大的后缀$f_{0,0,-1}$
class Solution:
def minimumValueSum(self, nums: List[int], andValues: List[int]) -> int:
n, m = len(nums), len(andValues)
msk = (1<<20)-1
@cache
def dfs(p, c, a):
if p == n or c == m:
return 0 if p == n and c == m else inf
if a&nums[p] < andValues[c] : return inf
res = dfs(p+1, c, a&nums[p])
if a&nums[p] == andValues[c]:
res = min(res, dfs(p+1, c+1, msk)+nums[p])
return res
ans = dfs(0, 0, msk)
return ans if ans != inf else -1