[C++] Share my DP solution (count the numbers without repeated digits)
\n// DP State is current digit index, visited bitmask,\n// comparison of current number to N, left digits.\nint dp[11][2048][3][11];\n\nint sgn(int val) {\n    
```\n// DP State is current digit index, visited bitmask,\n// comparison of current number to N, left digits.\nint dp[11][2048][3][11];\n\nint sgn(int val) {\n    return (0 < val) - (val < 0);\n}\n\nclass Solution {\npublic:\n\n    vector<int> N;\n    \n    int genAll(int curDigitIndex, int vis, int cmpN, int len) {\n       if (len == 0) {\n          return cmpN <= 0;\n       }\n       int &res = dp[curDigitIndex][vis][cmpN + 1][len];\n       if (res != -1) return res;\n       res = 0;\n       for (int i = 0; i <= 9; ++i) {\n          if (curDigitIndex == 0 && i == 0) continue;\n          if (vis & (1 << i)) continue;\n           \n          int nCmpN = cmpN \n              ? cmpN \n              : sgn(i - N[curDigitIndex]);\n           \n          res += genAll(\n              curDigitIndex + 1,\n              vis | (1 << i),\n              nCmpN,\n              len - 1);\n       }\n       return res;\n    }\n\n    int numDupDigitsAtMostN(int n) {\n      memset(dp, -1, sizeof(dp));\n      int nn = n;\n      while (nn) {\n          N.push_back(nn % 10);\n          nn /= 10;\n      }\n      reverse(N.begin(), N.end());\n\n      int allNonRep = 0;\n      for (int i = 1; i <= N.size(); ++i) {\n          int cmpN = i < N.size() ? -1 : 0;\n\t\t  // generate all numbers with non repeating\n\t\t  // digits with \'i\' length\n          allNonRep += genAll(0, 0, cmpN, i);\n      }\n      return n - allNonRep;\n    }\n};\n```
[]