Hard

题目描述

有 n 根长度不同的木棍，长度分别为 1 到 n 的整数。你想要排列这些木棍，使得从左边恰好能看到 k 根木棍。一根木棍从左边可见，当且仅当它左边没有更长的木棍。

例如，如果木棍排列为 [1,3,2,5,4]，那么长度为 1、3 和 5 的木棍从左边是可见的。

给定 n 和 k，返回满足条件的排列数。由于答案可能很大，请将其对 10^9 + 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 10^9 + 7) 种方式重新排列木棍，使得恰好 11 根木棍可见。

约束条件：

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

提示：

  • 是否有一种方法从基本情况构建解决方案？
  • 如果我们固定一根木棍的位置，有多少种方式？

解题思路

这是一个经典的动态规划问题，涉及第一类斯特林数的概念。

核心思路：

我们用 dp[i][j] 表示用 i 根木棍排列，恰好能看到 j 根的方案数。

状态转移分析：

考虑第 i 根木棍（长度为 i，是最长的）的位置：

  1. 放在最左边：由于它是最长的，一定可见，所以剩下 i-1 根木棍需要能看到 j-1 根

    • 贡献：dp[i-1][j-1]

  2. 不放在最左边：第 i 根木棍放在某个位置，不影响可见性（因为左边已有更高的木棍挡住）

    • 可以放在除第一个位置外的任意 i-1 个位置
    • 剩下 i-1 根木棍仍需看到 j 根
    • 贡献：(i-1) * dp[i-1][j]

递推关系：

dp[i][j] = dp[i-1][j-1] + (i-1) * dp[i-1][j]

边界条件：

  • dp[0][0] = 1（0 根木棍，看到 0 根的方案数为 1）
  • dp[i][0] = 0 (i > 0)（有木棍但看不到任何一根，不可能）
  • dp[0][j] = 0 (j > 0)（没有木棍但要看到木棍，不可能）

代码实现

class Solution {
public:
    int rearrangeSticks(int n, int k) {
        const int MOD = 1000000007;
        vector<vector<long long>> dp(n + 1, vector<long long>(k + 1, 0));
        
        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] + (long long)(i-1) * dp[i-1][j]) % MOD;
            }
        }
        
        return dp[n][k];
    }
};

class Solution:
    def rearrangeSticks(self, n: int, k: int) -> int:
        MOD = 10**9 + 7
        dp = [[0] * (k + 1) for _ in range(n + 1)]
        
        dp[0][0] = 1
        
        for i in range(1, n + 1):
            for j in range(1, min(i, k) + 1):
                dp[i][j] = (dp[i-1][j-1] + (i-1) * dp[i-1][j]) % MOD
        
        return dp[n][k]

public class Solution {
    public int RearrangeSticks(int n, int k) {
        const int MOD = 1000000007;
        long[,] dp = new long[n + 1, k + 1];
        
        dp[0, 0] = 1;
        
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= Math.Min(i, k); j++) {
                dp[i, j] = (dp[i-1, j-1] + (long)(i-1) * dp[i-1, j]) % MOD;
            }
        }
        
        return (int)dp[n, k];
    }
}

var rearrangeSticks = function(n, k) {
    const MOD = 1000000007;
    const dp = Array(n + 1).fill().map(() => Array(k + 1).fill(0));
    
    dp[0][0] = 1;
    
    for (let i = 1; i <= n; i++) {
        for (let j = 1; j <= Math.min(i, k); j++) {
            dp[i][j] = (dp[i-1][j-1] + (i-1) * dp[i-1][j]) % MOD;
        }
    }
    
    return dp[n][k];
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型值
时间复杂度O(n × k)
空间复杂度O(n × k)

说明：

  • 时间复杂度：需要填充 n × k 的二维数组，每个状态的计算为 O(1)
  • 空间复杂度：使用了 (n+1) × (k+1) 的二维数组存储状态

优化空间复杂度： 由于状态转移只依赖于前一行，可以使用滚动数组将空间复杂度优化到 O(k)。