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)  {
            if (lz) return state <= 1 ? 0 : 1;
            return state != 0;
        }
        int ub = (limit ? digits[pos] : 9);
        int ret = 0;
        if (lz == 0 && limit == 0 && dp[pos][state] != -1) return dp[pos][state];
        for (int i = 0; i <= ub; ++i) {
            if (i == 0) {
                if (lz == 0) {
                    if ((state & 0x01) == 0) {
                        ret += search(pos - 1, 0, 0, state | 1);
                    }
                } else {
                    ret += search(pos - 1, 0, lz, state);
                }
            } else {
                if (((1 << i) & state) == 0) {
                    int li = search(pos - 1, limit && i == ub, 0, state | (1 << i));
                    ret += li;
                }
            }
        }

        if (state == (1 << 4) + (1 << 0)) {
            printf("limit:%d lz:%d ret:%d st:%d\n", limit, lz, ret, state);
        }
        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;
    }
};