1. 问题描述
我们有 N 块高度唯一且从 1 到 N 的积木。目标是计算有多少种方式可以将它们排成一行，使得恰好有 L 块从左边可见，R 块从右边可见。
可见性定义
- 一块积木如果其左边没有比它高的积木，则从左边可见；
- 同理，如果其右边没有比它高的积木，则从右边可见。
举个例子
排列 [1, 3, 2, 5, 4] 中：
- 左边可见的有：1、3、5；
- 右边可见的有：4、5；
- 最高积木 5 在两边都可见。
2. 只考虑左边可见的情况
设 f(N, L) 表示 N 块积木中恰好有 L 块从左边可见的排列数。
我们可以通过动态规划来解决这个问题：
递推关系
- 把最高积木放在最后：此时它一定可见，问题变为在 N-1 块中选出 L-1 块可见；
- 把其他积木放在最后：此时最高积木不在最后，不能算作可见块，问题变为在 N-1 块中选出 L 块可见；
- 总共有 (N-1) 种非最高积木可以放在最后。
所以递推式为：
f(N, L) = f(N-1, L-1) + (N-1) * f(N-1, L)
边界条件
f(1, 1) = 1（只有一个积木，只有一种可见方式）f(1, k) = 0（k > 1 时不可能有超过一块可见）
Java 实现
public class BlockArrangement {
public static long arrangeBlocksLeft(int N, int L) {
long[][] dp = new long[N + 1][L + 1];
dp[1][1] = 1;
for (int n = 2; n <= N; n++) {
for (int l = 1; l <= L; l++) {
dp[n][l] = dp[n - 1][l - 1] + (n - 1) * dp[n - 1][l];
}
}
return dp[N][L];
}
}
✅ 时间复杂度分析
- 两层循环，时间复杂度为
O(NL)
3. 同时考虑左右可见的情况
我们现在要解决更复杂的问题：N 块积木中，L 块从左边可见，R 块从右边可见的排列数。
关键观察
- 最高积木是唯一在两边都可见的；
- 它左边有
L - 1块可见积木； - 它右边有
R - 1块可见积木； - 所以总共有
L + R - 2块可见积木分布在最高积木左右。
组合思想
- 我们可以先计算
f(N-1, L+R-2)，即在 N-1 块中安排L+R-2块可见的排列； - 然后从这
L+R-2块中选出R-1块放到右边； - 组合数为：
C(L+R-2, R-1)
最终公式
result = C(L+R-2, R-1) * f(N-1, L+R-2)
Java 实现
public class BlockArrangement {
public static long arrangeBlocks(int N, int L, int R) {
if (L + R - 2 >= N || L <= 0 || R <= 0) return 0;
long numerator = factorial(L + R - 2);
long denominator = factorial(L - 1) * factorial(R - 1);
return (numerator / denominator) * arrangeBlocksLeft(N - 1, L + R - 2);
}
public static long factorial(int n) {
long result = 1;
for (int i = 2; i <= n; i++) {
result *= i;
}
return result;
}
public static long arrangeBlocksLeft(int N, int L) {
long[][] dp = new long[N + 1][L + 1];
dp[1][1] = 1;
for (int n = 2; n <= N; n++) {
for (int l = 1; l <= L; l++) {
if (l <= n)
dp[n][l] = dp[n - 1][l - 1] + (n - 1) * dp[n - 1][l];
}
}
return dp[N][L];
}
}
✅ 时间复杂度分析
- 阶乘计算：
O(L + R) - DP 计算：
O(N(L + R)) - 总体时间复杂度：
O(N(L + R))
4. 总结
我们通过动态规划解决了“左边可见积木数”的问题，并将其扩展到同时考虑左右可见的情况。核心思想是：
- 利用递推关系快速构建状态表；
- 利用组合数学将左右可见问题转化为更小的子问题；
- 整体算法时间复杂度为
O(N(L + R))，在合理范围内。
✅ 踩坑提醒：
- 注意边界条件，如
L + R - 2 >= N时无解； - 阶乘除法要防止整数溢出（Java 中可使用
BigInteger）； - 动态规划数组初始化要小心索引越界。