Number of Ways to Rearrange Sticks With K Sticks Visible LeetCode solution in C++

1
#define ll long long
2
class Solution {
3
 public:
4
  vector<vector<ll>> dp;
5
  ll mod = 1e9 + 7;
6

7
  ll numWays(ll n, ll k) {
8
    if (k == 0 || k > n)
9
      return 0;           // can't have no stick visible or more sticks visible than the
10
                          // total number of sticks
11
    if (n <= 2) return 1; // base condition
12

13
    if (dp[n][k] != -1) return dp[n][k]; // return if already calculated
14

15
    ll ans = 0;
16

17
    // select the tallest stick
18
    ans = (ans + numWays(n - 1, k - 1)) % mod;
19

20
    // select any of the n - 1 sticks that are not the tallest
21
    ans = (ans + ((n - 1) * numWays(n - 1, k))) % mod;
22

23
    return dp[n][k] = ans;
24
  }
25

26
  int rearrangeSticks(int n, int k) {
27
    dp = vector<vector<ll>>(n + 1, vector<ll>(k + 1, -1));
28
    return numWays(n, k);
29
  }
30
};