Count Numbers with Unique Digits LeetCode solution in C++

1
// Recursion
2
class Solution {
3
 public:
4
  int solve(int n) {
5
    if (n == 0) return 1;
6
    int tmp = 9;
7
    int ans = 9;
8
    for (int i = 1; i < n; i++) ans *= tmp--;
9
    return dp[n] = ans + solve(n - 1);
10
  }
11
  int countNumbersWithUniqueDigits(int n) {
12
    return solve(n);
13
  }
14
};
15

16
// Memoization
17
class Solution {
18
 public:
19
  int dp[9] = {1};
20
  int solve(int n) {
21
    if (n == 0 || dp[n] != 0) return dp[n];
22
    int tmp = 9;
23
    int ans = 9;
24
    for (int i = 1; i < n; i++) ans *= tmp--;
25
    return dp[n] = ans + solve(n - 1);
26
  }
27
  int countNumbersWithUniqueDigits(int n) {
28
    return solve(n);
29
  }
30
};
31
// Dynamic Programming
32
class Solution {
33
 public:
34
  int countNumbersWithUniqueDigits(int n) {
35
    int sum = 1, c = 9;
36
    vector<int> dp(n + 2);
37
    dp[0] = 1, dp[1] = 10;
38
    for (int i = 2; i <= n; i++) {
39
      dp[i] = dp[i - 1] * c + sum;
40
      sum += dp[i - 1];
41
      c--;
42
    }
43
    return dp[n];
44
  }
45
};