Simple & Efficient C++ Digit DP solution with comments
Top Down multi-dimensional DP approach\n\n\n#define ll long long\n\nclass Solution {\npublic:\n    string s;\n    int dp[10][2][2][2][1<<10];\n\n    ll ff(int p
**Top Down multi-dimensional DP approach**\n\n```\n#define ll long long\n\nclass Solution {\npublic:\n    string s;\n    int dp[10][2][2][2][1<<10];\n\n    ll ff(int pos, bool tight, bool st, bool cnt, int mask) {\n        // If index reaches the length of the string return whether\n        // any repetition till now has been found or not?\n        if (pos == s.size()) return cnt ? 1 : 0;\n        \n        // Look in the DP table\n        if (dp[pos][tight][st][cnt][mask] != -1)\n            return dp[pos][tight][st][cnt][mask];\n\n        ll res = 0;\n        ll en = tight ? s[pos]-\'0\':9;\n\n        if (!st) {\n            // Place 0s, go to the rightmost\n            res = ff(pos+1, tight&s[pos]==\'0\', st, cnt, mask);\n            for (ll i=1; i<=en; i++) {\n                // Start the number, st = true\n                res += ff(pos+1, tight&(i==en), st|(i > 0), cnt, mask|1<<i);\n            }\n        }else {\n            // Number has started\n            for (ll i=0; i<=en; i++) {\n                // If number is found repeated, check using bitmask (mask & (1 << i))\n                // Make the cnt = true, i.e. cnt | mask&(1<<i)\n                res += ff(pos+1, tight&(i==en), st, cnt|(mask&(1<<i)), mask|1<<i);\n            }\n        }\n\n        return dp[pos][tight][st][cnt][mask] = res;\n    }\n\n    int numDupDigitsAtMostN(int N) {\n        s = to_string(N);\n        memset(dp, -1, sizeof dp);\n        return ff(0, true, false, false, 0);\n    }\n};\n```\n\nRead more about **Digit DP:**\nhttps://codeforces.com/blog/entry/53960
[]