给你正整数 low ，high 和 k 。
如果一个数满足以下两个条件，那么它是 美丽的 ：
- 偶数数位的数目与奇数数位的数目相同。
- 这个整数可以被 k 整除。
请你返回范围 [low, high] 中美丽整数的数目。
1. 数位dp
class Solution {
public:
int calc(int num,int k) {
string s = to_string(num);
int m = s.length(), memo[m][k+1][m][m];
memset(memo, -1, sizeof(memo)); // -1 表示没有计算过
function<int(int,int,int,int,bool,bool)> f = [&](int i, int odd, int even, int cur, bool is_limit, bool is_num) -> int {
if (i == m )
return is_num&even==odd&cur==0; // is_num 为 true 表示得到了一个合法数字
if (!is_limit && is_num && memo[i][cur][odd][even] != -1)
return memo[i][cur][odd][even];
int res = 0;
if (!is_num) // 可以跳过当前数位,表示前面全为0
res = f(i + 1, odd, even, cur ,false, false);
int up = is_limit ? s[i] - '0' : 9;
for (int d = 1 - is_num; d <= up; ++d) // 枚举要填入的数字 d
res = res + f(i + 1, odd+(d%2==1), even+(d%2==0),(cur*10+d)%k, is_limit && d == up, true);
if (!is_limit && is_num)
memo[i][cur][odd][even] = res;
return res;
};
return f(0, 0, 0,0, true, false); //从第0位开始，前面有0个奇数，当前累计值为0， 受限，不合法
cout<<endl;
}
int numberOfBeautifulIntegers(int low, int high, int k) {
return calc(high,k)-calc(low-1,k);
}
};