4408. 李白打酒加强版（dp）
话说大诗人李白，一生好饮。
幸好他从不开车。
一天，他提着酒壶，从家里出来，酒壶中有酒 2斗。
他边走边唱：
无事街上走，提壶去打酒。
逢店加一倍，遇花喝一斗。
这一路上，他一共遇到店 N次，遇到花 M 次。
已知最后一次遇到的是花，他正好把酒喝光了。
请你计算李白这一路遇到店和花的顺序，有多少种不同的可能？
注意：壶里没酒 (0 斗) 时遇店是合法的，加倍后还是没酒；但是没酒时遇花是不合法的。
输入格式
第一行包含两个整数 N 和 M。
输出格式
输出一个整数表示答案。由于答案可能很大，输出模 1000000007 的结果。
数据范围
对于 40%的评测用例：1≤N,M≤10。
对于 100% 的评测用例：1≤N,M≤100。数据范围
对于 40% 的评测用例：1≤N,M≤10。
对于 100%的评测用例：1≤N,M≤100。输入样例：
5 10输出样例：
14样例解释
如果我们用 0 代表遇到花，1 代表遇到店，14种顺序如下：
010101101000000 010110010010000 011000110010000 100010110010000 011001000110000 100011000110000 100100010110000 010110100000100 011001001000100 100011001000100 100100011000100 011010000010100 100100100010100 101000001010100
思路：dp，因为n和m的范围都很小，我们考虑用状态来表示，dp[i][j][k][c]表示经过i个店，j个花，酒有k斗，最后停留在c的方案数。这样我们很容易可以得到状态转移方程：
(1)当c=0&&k/2==0&&p==0 :dp[i][j][k][p]=(dp[i-1][j][k/2][0]+dp[i-1][j][k/2][1])%mod
意思是当前停留在店，那上一个状态就应该是i-1,因为停留在店酒的斗数会加倍，所以该状态的酒斗数应该是偶数，上一个状态的停留在哪里是不用管的。
（2）c=1&&p==1: dp[i][j][k][p]=(dp[i][j-1][k+1][0]+dp[i][j-1][k+1][1])%mod;
意思是当前停留在花，那上一个状态应该是j-1,因为停留在花处酒的斗数会减一，所以是从k+1转移过来的。
注意初始化，题目中说刚开始是有2斗酒，但是不能同时在店或者花处，二选一为1即可。
对于酒的斗数枚举到m是因为题目中说最后酒喝完了，所以酒的斗数一定不超过遇见的花的数量。
#include<bits/stdc++.h>
using namespace std;const int N=110;
const int mod=1e9+7;int dp[N][N][N][2];//dp[i][j][k][c]表示遇到店n次，花m次，酒k斗，最后停留在c的方案数
int n,m;int main()
{cin>>n>>m;for(int i=0;i<=n;i++){for(int j=0;j<=m;j++){for(int k=0;k<=m;k++){for(int p=0;p<2;p++){if(i==0&&j==0){dp[0][0][2][1]=1;continue;}if(i&&k%2==0&&p==0){dp[i][j][k][p]=(dp[i-1][j][k/2][0]+dp[i-1][j][k/2][1])%mod;}if(j&&p==1){dp[i][j][k][p]=(dp[i][j-1][k+1][0]+dp[i][j-1][k+1][1])%mod;}} }}}cout<<dp[n][m][0][1]<<endl;
}