1. 项目概述：搭积木问题的算法挑战
这道来自蓝桥杯2018年国赛B组的题目，表面看是儿童积木游戏，实则是考察选手对动态规划与前缀和优化的综合应用能力。题目要求计算在特定约束条件下，用方块搭建成符合"稳定金字塔"形状的所有可能方案数。这里的"稳定"意味着上层方块必须完全位于下层方块支撑范围内，这直接对应着算法中需要处理的重叠区间约束条件。
作为一道标为"普及+"难度的竞赛题，它完美展现了如何将生活场景抽象为数学模型的过程。我在第一次接触这类问题时，花了整整三天才彻底理解状态转移方程的推导逻辑。本文将拆解这个思考过程，重点分享如何通过前缀和优化将O(n^5)的暴力解法优化到O(n^3)的可计算范围。
2. 问题建模与基础解法
2.1 题目约束条件解析
给定一个最大宽度为m，总高度为n的积木塔，需要满足以下核心约束：
- 每层方块必须连续排列
- 第i层的方块必须完全包含在第i-1层方块的投影范围内
- 最底层必须铺满整个m宽度
例如当m=3，n=2时，所有有效搭建方式如下图所示：
■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■对应三种合法方案。
2.2 暴力DP解法设计
定义dp[i][l][r]表示第i层使用区间[l,r]方块的方案数。状态转移方程为：
dp[i][l][r] = sum(dp[i-1][a][b] for all a≤l≤r≤b)这意味着需要四重循环：
- 遍历所有层数i（1~n）
- 遍历当前层左边界l（1~m）
- 遍历当前层右边界r（l~m）
- 遍历前一层的所有可能区间[a,b]满足a≤l≤r≤b
这种实现时间复杂度高达O(n*m^4)，当m=100时根本无法计算。
3. 前缀和优化策略
3.1 二维前缀和预处理
观察到内层循环的本质是求一个二维区域和，这正是前缀和的用武之地。我们定义：
prefix[i][l][r] = sum(dp[i][a][b] for a<=l and b>=r)通过以下递推关系可在O(m^2)时间内完成预处理：
prefix[i][l][r] = dp[i][l][r] + prefix[i][l-1][r] + prefix[i][l][r+1] - prefix[i][l-1][r+1]3.2 优化后的状态转移
现在状态转移可以简化为：
dp[i][l][r] = prefix[i-1][l][r]将时间复杂度从O(m^4)降为O(m^2)的预处理，整体复杂度优化到O(n*m^2)。
关键技巧：这里的前缀和定义与常规不同，是"包含区域和"而非"前缀区域和"，需要特别注意递推方向。
4. 实现细节与边界处理
4.1 初始化条件
最底层(i=1)只有一种搭建方式：
for l in 1..m: for r in l..m: dp[1][l][r] = 1 if l==1 and r==m else 04.2 递推顺序优化
计算prefix时需要注意遍历顺序：
for l from 1 to m: for r from m downto l: # 反向遍历 prefix[i][l][r] = dp[i][l][r] + prefix[i][l-1][r] + prefix[i][l][r+1] - prefix[i][l-1][r+1]4.3 最终结果统计
所有顶层的可能区间之和即为答案：
result = sum(dp[n][l][r] for all 1≤l≤r≤m)5. 复杂度分析与优化验证
5.1 时间复杂度对比
| 方法 | 时间复杂度 | m=100时的计算量 |
|---|---|---|
| 暴力DP | O(n*m^4) | 10^10 |
| 前缀和优化 | O(n*m^2) | 10^6 |
5.2 空间优化技巧
由于每次只用到前一层的prefix，可以压缩空间到O(m^2)：
prev_prefix = initialize() for i from 2 to n: new_dp = compute(prev_prefix) prev_prefix = update_prefix(new_dp)6. 常见错误与调试技巧
6.1 典型错误案例
前缀和方向错误：正向计算prefix会导致重复计数
# 错误示例 for l from 1 to m: for r from l to m: # 应该反向边界条件遗漏：未处理l=1或r=m时的越界情况
# 正确做法 prefix[i][0][r] = 0 prefix[i][l][m+1] = 0
6.2 调试建议
- 先用小数据(m≤5)手动计算验证
- 打印各层dp矩阵检查对称性
- 对prefix矩阵进行差分验证
7. 代码实现示例（Python）
MOD = 10**9 + 7 def solve(m, n): # 初始化dp和prefix dp_prev = [[0]*(m+2) for _ in range(m+2)] prefix_prev = [[0]*(m+2) for _ in range(m+2)] # 第一层初始化 dp_prev[1][m] = 1 for l in range(1, m+1): for r in range(m, l-1, -1): prefix_prev[l][r] = (dp_prev[l][r] + prefix_prev[l-1][r] + prefix_prev[l][r+1] - prefix_prev[l-1][r+1]) % MOD for _ in range(2, n+1): dp_curr = [[0]*(m+2) for _ in range(m+2)] # 计算当前层dp for l in range(1, m+1): for r in range(l, m+1): dp_curr[l][r] = prefix_prev[l][r] # 更新prefix prefix_curr = [[0]*(m+2) for _ in range(m+2)] for l in range(1, m+1): for r in range(m, l-1, -1): prefix_curr[l][r] = (dp_curr[l][r] + prefix_curr[l-1][r] + prefix_curr[l][r+1] - prefix_curr[l-1][r+1]) % MOD dp_prev, prefix_prev = dp_curr, prefix_curr return sum(dp_prev[l][r] for l in range(1, m+1) for r in range(l, m+1)) % MOD8. 算法扩展与应用
8.1 变种问题思考
- 非完全包含条件：如果允许上层比下层宽，只需修改转移条件
- 多层约束：增加相邻层宽度差不能超过k的限制
- 三维积木：引入深度维度，问题将升级为三维DP
8.2 实际工程应用
这种区间包含型DP在以下场景有类似应用：
- 日历调度中的会议安排
- 资源分配中的区间覆盖
- 图形渲染中的层级合并
我在实际项目中曾用类似思路解决过广告位动态布局问题，关键是将业务约束转化为区间包含关系。
