LC 1866. 恰有 K 根木棍可以看到的排列数目

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

这题如果开始计算阶乘的话，那么思路就错了，使用阶乘计算会出现许多重复的情况。

为了表面重复计算，我们处理的时候都是从低到高来处理木棍。dp[i][j] 表示前面i根木棍可以看到j根

后面说看到ith根，不是指从小到大的第ith根棍子，而是指ith这个位置上的棍子
如果可以看到ith根的话，那么数量为dp[i-1][j-1]
如果看不到ith的话，那么取前面(i-1)里面任意一个出来放在ith的最后，接下来就是从前面i-1个棍子里面看到j根，所以结果是 (i-1)* dp[i-1][j]

动态规划还是讲究某种计算顺序，在这个顺序下面进行子问题最优化求解。

class Solution:
    def rearrangeSticks(self, n: int, k: int) -> int:
        dp = [[0] * (1 + k) for _ in range(n + 1)]
        dp[0][0] = 1

        for k2 in range(1, k + 1):
            for i in range(1, n + 1):
                dp[i][k2] = dp[i - 1][k2 - 1] + (i - 1) * dp[i - 1][k2]

        ans = dp[n][k]
        MOD = 10 ** 9 + 7
        return ans % MOD