【李白打酒加强版——DP】
题目
思路
三个注意点：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];
}