BinarySearch 1007 Visible Blocks

Problem statement

https://binarysearch.com/problems/Visible-Blocks/

Solution

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

Complexity

It is O(nk) for time and space.

Code

class Solution:
    def solve(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)
        return dp(n, k)