题意理解

有 N 堆草堆排成一行，高度为 h₁, h₂, …, h_N。允许的操作：如果相邻两堆高度差恰好为 1，可以将较高草堆顶部的草移到较低草堆上。求通过有限次操作可以得到的不同高度序列的数量（对 10⁹+7 取模）。

关键观察：操作不会改变草堆的总高度，只是重新分配。

核心思路

操作的本质分析

1. 操作可逆性：移动操作是可逆的，因此所有可达的序列构成一个连通分量
2. 约束条件：只有高度差为 1 的相邻草堆可以交换"单位高度"
3. 问题转化：这实际上是一个受限的排列计数问题

重要性质

设总高度 S = ∑h_i，平均高度为 S/N（可能不是整数）。

• 操作保持每个位置的高度在整数范围内变化
• 最终序列必须满足与原序列相同的总和约束
• 相邻位置的高度差限制了可能的转移

算法框架

动态规划解法

使用区间DP或线性DP：

状态设计： 设 dp[i][j] 表示考虑前 i 个位置，第 i 个位置的高度为 j 时的方案数。

状态转移： dp[i][j] = ∑ dp[i-1][k]，其中 |j - k| ≤ 1 且转移合法。

组合计数方法

另一种思路是将问题视为：

1. 确定高度范围：找出每个位置可能的高度取值
2. 计数路径数：在高度变化图上计数从起点到终点的路径数
3. 生成函数：使用生成函数来编码高度变化的过程

关键技巧

1.高度归一化

由于原始高度可能很大，但实际有效的高度范围有限，可以进行离散化或相对高度处理。

2.前缀和优化

DP转移通常可以前缀和优化到 O(1) 每次转移。

3.边界处理

需要仔细处理序列开头和结尾的特殊情况。

复杂度分析

• 时间复杂度：O(N·H) 或 O(N²)，其中 H 是高度范围
• 空间复杂度：O(N·H) 或 O(N)（使用滚动数组）

总结

本题的核心在于：

1. 理解操作的限制条件及其对序列可达性的影响
2. 将物理操作转化为组合计数模型
3. 设计高效的动态规划算法统计合法序列

这是一个典型的组合计数与动态规划结合的问题，考察选手将实际问题抽象为数学模型的能力。