范围中美丽整数的数目

给你正整数 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);
    }
};