题解

　　该题考察经典算法，可我还是太菜了...，不会做/(ㄒoㄒ)/~~。

       正解应该是 dp + 前缀和优化，只解 n == 1 或暴力 dp 都会超时，怎么看出来的呢?

       dp：

　　f[i][j][k] 表示第 i 层在 [j, k] 区间搭积木的总方案数，dp 方程很显然是 f[i][j][k] = f[i][j][k] + f[i - 1][x][y]; 其中 [j, k] 区间不存在不可放的位置，这是暴力 dp 的做法，时间复杂度为 $O(n^5)$。

       前缀和优化：

       在上述图示中，第 i - 1 层 f[i - 1][x][y] 即 [x, y] 这一部分很显然可以用前缀和优化掉，只用了 $O(1)$的时间复杂度即可完成，二维前缀和初始化的公式为：s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + a[i][j]，求解子矩阵为：s[x2][y2] - s[x1 - 1][y2] - s[x2][y1 - 1] + s[x1 - 1][y1 - 1]，不熟悉的可以画图推一下，比较容易理解。

       时间复杂度为 $O(n^3)$，完全可以过。