What is the best approach to solve Number of Ways to Rearrange Sticks With K Sticks Visible?

Use state transition dynamic programming with dp[n][k] representing arrangements with exactly k visible sticks.

How do I handle large results in this problem?

Always apply modulo 10^9 + 7 after each DP calculation to prevent integer overflow.

Can the DP solution be optimized in space?

Yes, by using a rolling array, space can be reduced from O(n*k) to O(k) since only the previous row is needed.

What are common mistakes when defining the DP recurrence?

Mixing up the counts of visible and hidden sticks or misapplying the combinatorial factor (n-1) can lead to wrong answers.

Is there a way to verify the DP approach quickly?

Test small examples such as n = 3, k = 2 or n = 5, k = 5 to ensure the DP table produces correct counts.

#1866

Hard

auto_awesome状态·转移·动态规划

LeetCode 题解工作台

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

有 n 根长度互不相同的木棍，长度为从 1 到 n 的整数。请你将这些木棍排成一排，并满足从左侧可以看到恰好 k 根木棍。从左侧可以看到木棍的前提是这个木棍的左侧不存在比它更长的木棍。例如，如果木棍排列为 [ 1 , 3 ,2, 5 ,4] ，那么从左侧可以看到的就是长度分别为 1…

数学动态规划组合数学

题目描述

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

例如，如果木棍排列为 [1,3,2,5,4] ，那么从左侧可以看到的就是长度分别为 1、3 、5 的木棍。

给你 n 和 k ，返回符合题目要求的排列数目。由于答案可能很大，请返回对 10⁹ + 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⁹+ 7) 种能满足恰好有 11 根木棍可以看到的排列。

提示：

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

lightbulb

解题思路

方法一：动态规划

我们定义 $f[i][j]$ 表示长度为 $i$ 的排列中，恰有 $j$ 根木棍可以看到的排列数目。初始时 $f[0][0]=1$ ，其余 $f[i][j]=0$ 。答案为 $f[n][k]$ 。

考虑最后一根木棍是否可以看到，如果可以看到，那么它一定是最长的，那么它的前面有 $i - 1$ 根木棍，恰有 $j - 1$ 根木棍可以看到，即 $f[i - 1][j - 1]$ ；如果最后一根木棍不可以看到，那么它可以是除了最长的木棍之外的任意一根，那么它的前面有 $i - 1$ 根木棍，恰有 $j$ 根木棍可以看到，即 $f[i - 1][j] \times (i - 1)$ 。

因此，状态转移方程为：

f[i][j] = f[i - 1][j - 1] + f[i - 1][j] \times (i - 1)

最终答案为 $f[n][k]$ 。

时间复杂度 $O(n \times k)$ ，空间复杂度 $O(n \times k)$ 。其中 $n$ 和 $k$ 分别是题目中给定的两个整数。

1

2

3

4

5

6

7

8

9

10

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

speed

复杂度分析

指标	值
时间	complexity is O(n _k) due to iterating over all DP states. Space complexity is O(n_ k) for the DP table, which can be reduced to O(k) using rolling arrays. Each state only depends on the previous row.
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Focus on defining a clear DP state that represents visible sticks.
question_mark
Watch for off-by-one errors in indexing k or n during state transitions.
question_mark
Check modulo operations to prevent integer overflow on large inputs.

warning

常见陷阱

外企场景

error
Failing to account for sticks that are hidden, which affects the recurrence.
error
Incorrect base case initialization causing invalid results for small n or k.
error
Mixing up the visible and hidden stick counts in the DP formula.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Count arrangements with exactly k visible sticks from the right instead of the left.
arrow_right_alt
Compute arrangements for sticks with duplicate lengths while maintaining visibility counts.
arrow_right_alt
Generalize the problem to find arrangements with at least k visible sticks.

help

常见问题

外企场景

继续练习

#1916 统计为蚁群构筑房间的不同顺序 #1735 生成乘积数组的方案数 #2063 所有子字符串中的元音