这是一道经典的组合数学问题考察的是第一类斯特林数。题目要求计算将 n 根长度互不相同的木棍排列使得从左侧恰好能看到 k 根木棍的方案数。 核心思路我们使用动态规划来解决。定义 dp[i][j] 为使用长度为 1 到 i 的 i 根木棍恰好能看到 j 根的方案数。关键在于考虑长度为 i 的最长木棍应该放在哪里。1. 放在最左边* 因为它是最长的所以它一定会被看到。* 剩下的 i-1 根木棍在它右边我们需要从这 i-1 根中恰好看到 j-1 根。* 这种情况的方案数是 dp[i-1][j-1]。2. 放在其他 i-1 个位置即不是最左边* 它不会被看到。为什么因为它左边至少有一根木棍。虽然它是最长的但“可见”是指比左边所有木棍都长。然而这里有一个更深刻的组合数学解释这个问题的答案恰好等于第一类斯特林数。* 在斯特林数的语境下将最长的木棍插入到已有排列的非首位相当于将它插入到一个已有的“循环”中这不会增加循环的总数循环数对应可见木棍数。* 有 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] C语言代码实现includedefine MOD 1000000007int rearrangeSticks(int n, int k) {// 创建DP表dp[i][j]表示i根木棍恰好看到j根的方案数// 使用long long防止中间计算溢出long long** dp (long long**)malloc((n 1) * sizeof(long long*));for (int i 0; i n; i) {dp[i] (long long*)calloc(k 1, sizeof(long long));}// 初始化0根木棍看到0根方案数为1dp[0][0] 1;// 填充DP表for (int i 1; i n; i) {// j最多为i也最多为kfor (int j 1; j i j k; j) {// 状态转移方程// 1. 最长木棍放最前面它会被看到dp[i][j] dp[i - 1][j - 1];// 2. 最长木棍放其他位置不会增加可见数量dp[i][j] (dp[i][j] (i - 1) * dp[i - 1][j]) % MOD;}}int result (int)dp[n][k];// 释放内存for (int i 0; i n; i) {free(dp[i]);}free(dp);return result;} 示例验证以 n3, k2 为例1. dp[0][0] 12. i1: dp[1][1] dp[0][0] 0 * dp[0][1] 13. i2:* dp[2][1] dp[1][0] 1 * dp[1][1] 0 1 * 1 1 (排列: [2,1])* dp[2][2] dp[1][1] 1 * dp[1][2] 1 0 1 (排列: [1,2])4. i3:* dp[3][2] dp[2][1] 2 * dp[2][2] 1 2 * 1 3最终结果为 3对应的排列是 [1,3,2], [2,3,1], [2,1,3]都恰好能看到 2 根木棍。⏱️ 复杂度分析* 时间复杂度O(n*k)需要填充一个 n×k 的DP表。* 空间复杂度O(n*k)用于存储DP表。可以通过滚动数组优化到 O(k)但为了清晰起见这里使用了二维数组。