算法011-第一类斯特林数(恰有K根木棍可以看到的排列数目)

第一类斯特林数

第一类斯特林数常用于统计：n 个不同元素的排列中，恰好能拆成 k 个置换环的方案数。

记作：S(n,k)

它的递推式是：S(n,k)=S(n-1,k-1)+(n-1)S(n-1,k)

这个递推可以从加入新元素 n 来理解。

什么是环

假如原来的数列中：1,2,3,4,5，以这个方式排列，移动后有：2,1,5,4,3，其中对应关系是：1->2,2->1，5->3,3->5，4，所以这里就相当于有(1,2)(3,5)(4)共3个环。

新元素自己形成一个环

如果新增的元素自成一环，那么环数会增加 1。

所以原来的 n-1 个元素需要恰好有 k-1 个环：S(n-1,k-1) 变成现在有n个元素且有k个环，即：S(n,k)

新元素插入已有环

如果不希望环数增加，就把 n 插入已有某个环中。

例如：(1 4 2)，加入 7，就变成了(1 7 4 2)。

本质上只是把：1 → 4，改成：1 → 7 → 4。环的数量没有改变。

原来共有 n-1 个元素，每个元素后面都可以插入一次，因此有 n-1 个不同位置。

所以这一部分方案数为：(n-1)S(n-1,k)

最终得到：S(n,k)=S(n-1,k-1)+(n-1)S(n-1,k)

可见木棍

有 n 根长度互不相同的木棍，长度为从 1 到 n 的整数。请你将这些木棍排成一排，并满足从左侧可以看到恰好 k 根木棍。从左侧可以看到木棍的前提是这个木棍的左侧不存在比它更长的木棍。

例如，如果木棍排列为 [1,3,2,5,4] ，那么从左侧可以看到的就是长度分别为 1、3 、5 的木棍。给你 n 和 k ，返回符合题目要求的排列数目。由于答案可能很大，请返回对 109 + 7 取余的结果。

示例 1：

输入：n = 3, k = 2
输出：3
解释：[1,3,2], [2,3,1] 和 [2,1,3] 是仅有的能满足恰好 2 根木棍可以看到的排列。

示例 2：

输入：n = 5, k = 5
输出：1
解释：[1,2,3,4,5] 是唯一一种能满足全部 5 根木棍可以看到的排列。

示例 3：

输入：n = 20, k = 11
输出：647427950
解释：总共有 647427950 (mod 109 + 7) 种能满足恰好有 11 根木棍可以看到的排列。

提示：
1 <= n <= 1000
1 <= k <= n

放在最左边

新木棍 + 原排列

因为它左边没有任何木棍，所以它一定可见。

因此：原来 j-1 根可见 → 现在 j 根可见

所以它由dp[i-1][j-1]决定

放在其他位置

一共有 i 个插入位置，其中最左边已经算过，因此剩下i - 1个位置。

新木棍是最矮的，只要它前面存在木棍，它就一定不可见，同时也不会影响其他木棍。

所以可见数量不变：原来 j 根可见 → 现在仍然 j 根可见

因此由(i-1)dp[i-1][j]决定

于是：dp[i][j]=dp[i-1][j-1]+(i-1)dp[i-1][j]

这和第一类斯特林数的递推完全一致。

因此这道题本质上就是第一类斯特林数。

代码

class Solution {
public:
    int rearrangeSticks(int n, int k) {
        const int MOD = 1e9 + 7;

        vector<vector<long long>> dp(
            n + 1,
            vector<long long>(k + 1)
        );

        dp[0][0] = 1;

        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j <= min(i, k); ++j) {
                dp[i][j] =
                    dp[i - 1][j - 1]
                    + (i - 1) * dp[i - 1][j];

                dp[i][j] %= MOD;
            }
        }

        return dp[n][k];
    }
};

总结

第一类斯特林数：
新元素自己成环       → 环数 +1
新元素插入已有环     → 环数不变

可见木棍：
最矮木棍放最左       → 可见数 +1
最矮木棍放其他位置   → 可见数不变

因此两者拥有相同的状态转移。

AI真是个好东西，还能大部分替我总结