题意： 有m个方块，底层须放置n个方块，并且上方的方块放置不能出现凹槽。上图为m=6 n=3的示例，左边合法方案，右边非法。求合法的方案数量。
题解： 想来想去也只能用dp来写啊，就算是这样，状态转移方程也推了很久很久。定义状态dp[s][res]表示底层有s个方块，上方还需摆放res个方块的方法总数。 而当res - s > s时状态转移方程为：dp[s][res] = s * dp[1][res - 1] + (s - 1) * dp[2][res - 2] + ... + dp[s][res - s] 。 当res - s <= s 时状态转移方程为：dp[s][res] = s * dp[1][res - 1] + (s - 1) * dp[2][res - 2] + ... + (s - res + 1) * dp[res][0] 。
解释： 当需要放置s个方块作为底层，上方还需要放置res个方块时。我们上方的放置的选择有，即dp[s][res]：
底层放置一个方块：种类 + s * dp[1][res - 1]。（注意是上方的res个方块的底层，区别于前面所述的底层s）底层放置两个方块：种类 + (s - 1) * dp[2][res - 2]。···底层放置t = min(res, s)个方块：种类 + (s - t + 1) * dp[t][res - t]。如此递推直到res = 0时，种类为1。因为状态转移方程比较特殊，比较冗长，我们不可能真的去多写一个for循环来递推。所以又引用了前缀和来辅助求值。
补充： 之前写的时候只是随口提了一下借助前缀和，但是当我过几天再看这个代码的时候，越发觉得这个前缀和真的太秒了（代码是从别处学来的，所以不是自夸） 当s = 1时：
dp[1][0] = 1;dp[1][1] = dp[1][0] = 1; //1 + 0 = 1 (res)dp[1][2] = dp[1][1] = 1; //1 + 1 = 2 (res)dp[1][3] = dp[1][2] = 1; //1 + 2 = 3 (res)… 当s = 2时：dp[2][0] = 1;dp[2][1] = 2 * dp[1][0] = 2; //1 + 0 = 1 (res)dp[2][2] = 2 * dp[1][1] + dp[2][0] = 3; //1 + 1 = 2 + 0 = 2 (res)dp[2][3] = 2 * dp[1][2] + dp[2][1] = 4; //1 + 2 = 2 + 1 = 3 (res)…为了避免篇幅太长，所以只列出这么多，如果觉得不足以总结出规律的，读者可以复制代码之后自行打表观察。
总结： 横向比较时，dp[s][res]所加项都有一个特点，就是两个下标之和都等于res（其实这也算不上什么规律，因为前文我们就是这么分析，但是这一点对于求前缀和很有帮助）。纵向比较时，dp[s][res]所加项均在dp[s + 1][res]中重复出现，并且系数+1。规律已给出，代码中表现为sum和pre数组，需要读者自己多加思考。
#include<bits/stdc++.h> using namespace std; inline int read(){ int s = 0, w = 1; char ch = getchar(); while(ch < '0' || ch > '9'){if(ch == '-') w = -1; ch = getchar();} while(ch >= '0' && ch <= '9') s = s * 10 + ch - '0', ch = getchar(); return s * w; } const int N = 5e3 + 10; const int mod = 1e9 + 7; int sum[N]; int pre[N]; int dp[N][N]; void run(int n, int m){ for(int s = 1; s <= n; s++){ for(int res = 0; res <= m; res++){ pre[res] += sum[res]; if(pre[res] >= mod) pre[res] -= mod; if(res == 0) dp[s][res] = 1; else dp[s][res] = pre[res]; sum[s + res] += dp[s][res]; if(sum[s + res] >= mod) sum[s + res] -= mod; } } printf("%d\n", dp[n][m]); } int main(){ int n = read(), m = read(); run(n, m - n); return 0; }