Leetcode 1866. Number of Ways to Rearrange Sticks With K Sticks Visible

Problem statement

https://leetcode.com/problems/number-of-ways-to-rearrange-sticks-with-k-sticks-visible/

Solution

Here we can write it down as recurrence:

1. If the last element is the largest, we have dp(n - 1, k - 1) options.
2. If it is not the largest, then we have n-1 choices for the last element.

Complexity

It is O(nk) for time and space.

Code

class Solution:
    def rearrangeSticks(self, n, k):
        @lru_cache(None)
        def dp(n, k):
            if n == k: return 1
            if k == 0: return 0
            return (dp(n-1, k-1) + (n-1)*dp(n-1, k)) % (10**9 + 7)
        return dp(n, k)