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

Thinking process: Given stickCount sticks, how can we make visibleCount of them left visible?

Considering the stick we will put at the right most position among those stickCount sticks:
if we choose the tallest stick among those stickCount sticks: This selected stick will for sure be visible since it is the tallest among those sticks. Then the remaining problem is "Given stickCount-1 sticks, how can we make visibleCount-1 of them left visible?"
if don't choose the tallest stick for the right most position, then we can choose any of the remaining stickCount-1 sticks. No matter which one we choose, the selected stick won't be visible since the tallest one would block it. Then the remaining problem is "Given stickCount-1 sticks, how can we make visibleCount of them left visible?"

T = O(n * k)

    def rearrangeSticks(self, n: int, k: int) -> int:
        def helper(stickCount, visiableCount):
            if visiableCount <= 0 or stickCount < visiableCount:
                return 0
            if stickCount == visiableCount:
                return 1
            
            if dp[stickCount][visiableCount] != -1:
                return dp[stickCount][visiableCount]
            
            dp[stickCount][visiableCount] = (helper(stickCount-1, visiableCount-1) + (stickCount-1) * helper(stickCount-1, visiableCount)) % (10**9+7)
            
            return dp[stickCount][visiableCount]
        
        dp = [[-1] * (k+1) for _ in range(n+1)]
        return helper(n, k)

1866. Number of Ways to Rearrange Sticks With K Sticks Visible - cocoder39/coco39_LC GitHub Wiki