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

英文原文

There are n uniquely-sized sticks whose lengths are integers from 1 to n. You want to arrange the sticks such that exactly k sticks are visible from the left. A stick is visible from the left if there are no longer sticks to the left of it.

• For example, if the sticks are arranged [1,3,2,5,4], then the sticks with lengths 1, 3, and 5 are visible from the left.

Given n and k, return the number of such arrangements. Since the answer may be large, return it modulo 109 + 7.

 

Example 1:

Input: n = 3, k = 2
Output: 3
Explanation: [1,3,2], [2,3,1], and [2,1,3] are the only arrangements such that exactly 2 sticks are visible.
The visible sticks are underlined.

Example 2:

Input: n = 5, k = 5
Output: 1
Explanation: [1,2,3,4,5] is the only arrangement such that all 5 sticks are visible.
The visible sticks are underlined.

Example 3:

Input: n = 20, k = 11
Output: 647427950
Explanation: There are 647427950 (mod 109 + 7) ways to rearrange the sticks such that exactly 11 sticks are visible.

 

Constraints:

• 1 <= n <= 1000
• 1 <= k <= n

中文题目

有 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

通过代码

高赞题解

方法一：动态规划

思路与算法

我们用 $f(i, j)$ 表示长度为 $1, 2, \cdots, i$ 的木棍且可以可以看到其中的 $j$ 根木棍的方案数。

在进行状态转移的时候，我们可以考虑最后一根木棍是否可以被看到：

• 如果可以被看到，那么最后一根木棍的长度一定为 $i$，因此前 $i-1$ 根木棍的长度恰好为 $1, 2, \cdots i-1$ 的一个排列，并且可以看到其中的 $j-1$ 根木棍。这样就有状态转移方程：

  $$
  f(i, j) = f(i - 1, j - 1)
  $$

• 如果不可以被看到，那么最后一根木棍的长度为 $[1, i-1]$ 中的某个值。假设这个值为 $x$，那么前 $i-1$ 根木棍的长度为 $1, \cdots, x-1, x+1, \cdots, i$ 的一个排列，并且可以看到其中的 $j$ 根木棍。

  由于一根木棍能否被看到只与它和它左侧木棍的「相对高度关系」有关，而与「绝对高度关系」无关。因此如果我们将长度：

  $$
  1, \cdots, x-1, x+1, \cdots, i
  $$

  按照顺序重新分配为：

  $$
  1, 2, \cdots, i-1
  $$

  那么任意两根木棍的「相对高度关系」都保持不变，即我们仍然可以看到 $j$ 根木棍，满足要求的排列数为 $f(i-1, j)$，与 $x$ 的取值无关。这样就有状态转移方程：

  $$
  f(i, j) = (i-1) \cdot f(i-1, j)
  $$

将上面的两种情况求和，即可得到最终的状态转移方程：

$$
f(i, j) = f(i - 1, j - 1) + (i-1) \cdot f(i-1, j)
$$

最终的答案即为 $f(n, k)$。

细节

当 $i=0$ 时，我们没有使用任何木棍，所以看不到任何木棍，$f(i, 0)$ 的值为 $1$，除此之外的 $f(i, j)$ 的值为 $0$。

注意到状态转移方程中，$f(i, ..)$ 只会从 $f(i-1, ..)$ 转移而来，因此我们可以使用两个长度为 $k+1$ 的一维数组代替二维数组，交替地进行状态转移。

代码

[sol1-C++]
class Solution {
private:
    static constexpr int mod = 1000000007;
    
public:
    int rearrangeSticks(int n, int k) {
        vector<int> f(k + 1);
        f[0] = 1;
        for (int i = 1; i <= n; ++i) {
            vector<int> g(k + 1);
            for (int j = 1; j <= k; ++j) {
                g[j] = ((long long)f[j] * (i - 1) % mod + f[j - 1]) % mod;
            }
            f = move(g);
        }
        return f[k];
    }
};

[sol1-Python3]
class Solution:
    def rearrangeSticks(self, n: int, k: int) -> int:
        mod = 10**9 + 7

        f = [1] + [0] * k
        for i in range(1, n + 1):
            g = [0] * (k + 1)
            for j in range(1, k + 1):
                g[j] = (f[j] * (i - 1) + f[j - 1]) % mod
            f = g
        
        return f[k]

复杂度分析

• 时间复杂度：$O(nk)$。

• 空间复杂度：$O(k)$，即为两个一维数组需要使用的空间。

统计信息

通过次数	提交次数	AC比率
2366	3915	60.4%

提交历史

提交时间	提交结果	执行时间	内存消耗	语言