lc t4

class Solution {
    vector<vector<int>> dp;
    vector<int> digits;
    int dcnt;

    int search(int pos, int limit, int lz, int state) {
        // printf("in search pos:%d limit:%d lz:%d state:%d\n", pos, limit, lz, state);
        if (pos == -1) return state < 1 ? 0 : 1;
        int ub = limit ? digits[pos] : 9;
        int ret = 0;
        if (lz == 0 && limit == 0 && dp[pos][state] != -1) return dp[pos][state];

        if (lz == 1) ret += search(pos - 1, 0, lz, state);
        for (int i = 0; i <= ub; ++i) {
            if (((1 << i) & state) == 0) {
                if (i == 0) {
                    if (lz == 0)
                        ret += search(pos - 1, 0, 0, state | 1);
                } else {
                    ret += search(pos - 1, limit && i == ub, 0, state | (1 << i));
                }
            }
        }

        if (lz == 0 && limit == 0) dp[pos][state] = ret;
        return ret;
    }
public:
    int countSpecialNumbers(int n) {
        dp = vector<vector<int>>(1<<4, vector<int>(1 << 10, -1));
        int nn = n;
        dcnt = 0;
        digits = vector<int>(16);
        while(nn != 0) { digits[dcnt++] = nn % 10; nn /= 10; }
        int ans = search(dcnt - 1, 1, 1, 0);
        return ans;
    }
};