第四题动态规划解法

首先这题最好的做法肯定是用容斥
但是动态规划也是可行的，只是写起来麻烦很多
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];
    }
};