// 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，前导零存在后续的前导零才可以存在
}
数位dp类似题
这是一种记忆化搜索的新思路——构造合法的前缀，维护后缀最优/计数值。
$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