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

1
M = 10**9 + 7
2

3
from functools import cache
4

5

6
class Solution:
7
    def rearrangeSticks(self, n: int, k: int) -> int:
8
        return dp(n, k)
9

10

11
# consider the shortest
12
@cache
13
def dp(n, k):
14
    if n == k:
15
        return 1
16
    if n <= 0 or k <= 0:
17
        return 0
18
    return (dp(n - 1, k - 1) + (n - 1) * dp(n - 1, k)) % M
19

20

21
# `dp(n, k)` indicates the number of arrangements of `n` distinct sticks with exactly `k` visible sticks.
22
# Those `n` **distinct** sticks does NOT have to be numbered from `1` to `n` consecutively.