首先这题最好的做法肯定是用容斥
但是动态规划也是可行的,只是写起来麻烦很多
f[i][j][l][r]代表做完前i行,满足下三个条件的方案数:
1、前i行一共放了j个石头
2、l = (左边一列是否有石头)
3、r = (右边一列是否有石头)
边界为 f[0][0][0][0] = 1
然后从前往后枚举每一行,考虑转移
转移的时候首先需要枚举当前行放多少石头,然后枚举l, r的变化状况,在这个过程中需要统计这一行:
1、有多少个格子必须放石头 (设有mid个)
2、有多少个格子可以放也可以不放 (设有need个)
首先中间的m - 2个格子肯定是可放可不放的,所以一开始mid = m - 2,然后对于左右两边的状态变化:
1、0 -> 0,那必定不能放
2、0 -> 1, 必定要放,need++
3、1 -> 1,无所谓,mid++
然后转移的方案数就是mid个格子中挑选(当前行放的石头数- need)个格子,用预处理的组合数计算即可。

class Solution {
public:
    int MOD = 1e9 + 7;
    int C[33][33];
    int f[33][1005][2][2];

    int solve(int n, int m, int k) {
        for (int i = 0; i <= 30; i++) {
            C[i][0] = C[i][i] = 1;
            for (int j = 1; j < i; j++) {
                C[i][j] = (C[i - 1][j - 1] + C[i - 1][j]) % MOD;
            }
        }
        for (int i = 0; i <= n; i++) {
            for (int j = 0; j <= k; j++) {
                for (int l = 0; l < 2; l++) {
                    for (int r = 0; r < 2; r++) {
                        f[i][j][l][r] = 0;
                    }
                }
            }
        }
        f[0][0][0][0] = 1;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j <= k; j++) {
                for (int l = 0; l < 2; l++) {
                    for (int r = 0; r < 2; r++) {
                        for (int now = 0; now <= m && j + now <= k; now++) {
                            if ((i == 0 || i == n - 1) && now == 0) {
                                continue;
                            }
                            for (int ll = l; ll < 2; ll++) {
                                for (int rr = r; rr < 2; rr++) {
                                    int mid = (m - 2), need = 0;
                                    if (l == 1) {
                                        mid++;
                                    } else {
                                        if (ll == 0) {

                                        } else {
                                            need++;
                                        }
                                    }
                                    if (r == 1) {
                                        mid++;
                                    } else {
                                        if (rr == 0) {

                                        } else {
                                            need++;
                                        }
                                    }
                                    if (need > now || need + mid < now) {
                                        continue;
                                    }
                                    (f[i + 1][j + now][ll][rr] += (long long)f[i][j][l][r] * C[mid][now - need] % MOD) %= MOD;
                                }
                            }
                        }
                    }
                }
            }
        }
        return f[n][k][1][1];
    }
};