题目

思路

三个注意点：k是偶数的状态才能是遇到店之后的状态、f[n-1][m][k]状态非法、不要越界

代码

#include <bits/stdc++.h>
using namespace std;
const int N = 110, mod = 1e9+7;
int f[N][N][N];
int main()
{
    int n, m;
    cin >> n >> m;
    
    f[0][0][2] = 1;
    for(int i = 0; i <= n; i++)
    {
        for(int j = 0; j <= m; j++)
        {
            for(int k = 0; k <= m; k++)
            {
                if(j-1 >= 0) f[i][j][k] = f[i][j-1][k+1];
                if(i-1 >= 0 && k % 2 == 0) f[i][j][k] = (f[i][j][k] + f[i-1][j][k/2]) % mod;
                if(i == n-1 && j == m) f[i][j][k] = 0;
            }
        }
    }
    
    cout << f[n][m][0];
}