蓝桥杯备赛Day12 动态规划1基础

动态规划

动态规划基础

动态规划将复杂问题分解成很多重叠的子问题，再通过子问题的解得到整个问题的解
分析步骤:
确定状态:dp[i][j]=val,“到第i个为止，xx为j的方案数/最小代价/最大价值”
状态转移方程:
确定最终状态
要求:
(1)最优子结构
(2)无后效性:已经求解的子问题，不会再受到后续决策的影响。
(3)子问题重叠，将子问题的解存储下来
两种思路:
(1)按题目

线性DP

数字三角形

学习:
(1)将整个大问题分解为一个小问题，就是a[i][j]位置肯定向max(a[i+1][j],a[i+1][j+1])的位置走，所以设置状态dp[i][j]，表示从第i行第j列位置往下走的所有路径的数字和的最大值,可以得到状态转移方程dp[i][j]=a[i][j]+max(dp[i+1][j],dp[i+1][j+1])，然后自底向上遍历，得到最终状态dp[0][0]
代码:

#include <bits/stdc++.h>using namespace std;const int N=105;
int n,a[N][N],dp[N][N];int main(){ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);cin>>n;for(int i=0;i<n;i++){for(int j=0;j<=i;j++){cin>>a[i][j];}}for(int i=n-1;i>-1;i--){for(int j=0;j<=i;j++){dp[i][j]=a[i][j]+max(dp[i+1][j],dp[i+1][j+1]); //状态转移方程 }}cout<<dp[0][0];return 0;
}

破损的楼梯

学习:
(1)状态dp[i]表示走到第i级台阶的方案数，可以有第i-1级台阶或者第i-2级台阶走到，所有得到状态转移方程dp[i]=dp[i-1]+dp[i-2]，得到最终状态dp[n],不能从第n级台阶向下写状态转移方程dp[i]=dp[i+1]+dp[i+2]，因为这样你已经前提假设能走到第n级台阶了，不能走到的情况输出0是错误的
代码:

#include <bits/stdc++.h>using namespace std;
const int N=1e5+10;
const long long p=1e9+7;
int n,m,dp[N]; //状态为从0级台阶走到第i级台阶的方案数 
bool mark[N]; //损坏的台阶为true int main(){ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);cin>>n>>m;for(int i=0;i<m;i++){int t;cin>>t;mark[t]=true;}dp[0]=1;//第1级台阶特殊，只能从0级到达 if(!mark[1])	dp[1]=1;for(int i=2;i<=n;i++){//是破损台阶，跳过if(mark[i]) continue;//不是破损台阶，写状态转移方程//第i级台阶可以由第i-1级台阶或者第i-2级台阶到达 //说明第i级台阶的方案数为第i-1级台阶的方案数加第i-2级台阶的方案数之和//破损台阶方案数为0 dp[i]=(dp[i-1]+dp[i-2])%p; }cout<<dp[n];return 0;
}

安全序列

学习思路1:
(1)此题跟上面不一样，dp[i]表示以i结尾的方案和（这个思想可以学习），比如(1,4)是以4结尾的方案，而(0)就是全都不放的一种方案，所以状态转移方程为$$dp[i]=\sum _{j=0}^{i-k-1}dp[j]$$
,其中i-k-1>=0才要这样转移，例如k=2时，以4结尾的方案有(0,4)(1,4)，而不转移的dp都是1，如(0),(1)，再利用前缀和优化$$prefix[i]=\sum _{j=0}^{i}dp[j]$$
代码:

#include <bits/stdc++.h>using namespace std;typedef long long ll;
const int N=1e6+10,p=1e9+7;
int n,k;
ll dp[N],prefix[N]; //dp[i]表示以i结尾(最后一个放1的位置)的方案个数,状态转移方程为dp[i]=dp[0]+...+dp[i-k-1],所以需要前缀和prefix[i]=dp[0]+..+dp[i] 
int main(){ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);cin>>n>>k;//以0结尾的方案个数为1(全不放，全为0) ,prefix[-1]无意义，所以要提前初始化dp[0]=prefix[0]=1;for(int i=1;i<=n;i++){//当i-k-1>=0时，才有状态转移,反之都是1 if(i-k-1<0)	dp[i]=1;else	dp[i]=prefix[i-k-1]; //不用减prefix[-1]prefix[i]=(prefix[i-1]+dp[i])%p;}cout<<prefix[n]; //结果不是dp[n],不是以n结尾的方案和，而是dp[0]+...+dp[n] return 0;
}

学习思路2:
(1)直接用dp[i]来表示共i个空位的方案和，而这一位可以放，也可以不放，方案和=第i位不放的方案+第i位放的方案，第i位不放的方案没有限制条件，就是dp[i-1],而第i位放的方案与i-k-1和0的大小有关。如果i-k-1<0,说明不用考虑隔开k个位置的限制，放就是方案数+1，而如果i-k-1>=0，说明要考虑隔开k个位置的限制，方案数为dp[i-k-1]，分情况得到状态转移方程
代码:

#include <bits/stdc++.h>using namespace std;typedef long long ll;
const int N=1e6+10,p=1e9+7;
int n,k;
ll dp[N]; //dp[i]表示共i个空位的方案和，等于该位置放+不放的方案和 
int main(){ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);cin>>n>>k;dp[0]=1;for(int i=1;i<=n;i++){//当i-k-1<0时，放就是直接加1，不放就是dp[i-1], if(i-k-1<0)	dp[i]=(dp[i-1]+1)%p;//当i-k-1>=0时，放的时候才要考虑dp[i-k-1]，才有意义，不放就是dp[i-1] else	dp[i]=(dp[i-1]+dp[i-k-1])%p; }cout<<dp[n]; return 0;
}

二维DP

dp数组为二维,描述dp状态的变量不止一个

摆花

学习:
(1)状态dp[i][j]表示到第i种花为止(不一定以第i种花结尾，即不一定摆第i种花)，到第j位为止，摆花的方案，因为第i种花可以摆0-a[i]盆，所有dp[i][j]由dp[i-1][j-k],k=0-a[i]这些状态转移而来，相加,图示:
![[摆花.png]]转移方程为:$$dp[i][j]=\sum _{k=0}^{k=a[i]}a[i-1][j-k]$$
注意初始状态dp[0][0]=1,以及k<=min(j,a[i]),以及不用+=,因为要取模
代码:

#include <bits/stdc++.h>using namespace std;
const int N=105,p=1e6+7;
int n,m,a[N],dp[N][N]; //dp[i][j]表示到第i种花为止，到第j位为止，摆花的方案数 int main(){ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);cin>>n>>m;for(int i=1;i<=n;i++)	cin>>a[i];//初始化dp[0][0]=1,不摆也是一种方案dp[0][0]=1;//状态转移方程 for(int i=1;i<=n;i++){ //从第1种花开始，到第n种花 for(int j=0;j<=m;j++){ //从第0位开始，到第m位//状态转移 int t=min(a[i],j); //第i种花最多摆放min(a[i],j]盆 for(int k=0;k<=t;k++){ //第i种花可以摆0-t盆 dp[i][j]=(dp[i][j]+dp[i-1][j-k])%p;//因为要取余，所有不用+= }}} cout<<dp[n][m];return 0;
}

选数异或

学习:
(1)这题跟摆花一样，先区分一下子序列和子串的区别:
子序列不一定要求连续，而子串要求连续，两个都要求顺序跟原来一样
dp[i][j]表示到第i个数字为止(不一定以第i个数字结尾，即子序列不一定包括第i个数字),到异或和值为j为止的子序列总数
状态转移方程就是第i-1个数字转移到第i个数字，取第i个数字+不取第i个数字的和:$$dp[i][j]=dp[i-1][j\text{^}a[i]]+dp[i-1][j]$$
(2)dp[0][0]=1,因为空子序列的异或和是0，是一个子序列方案
(3)题目说0<=a[i]<63,根据异或性质，异或和不会超过63(63=2^6-1=111111),不管怎么异或都不会超过63，所有能开dp[N][70],j也能从0开始遍历到70
代码:

#include <bits/stdc++.h>using namespace std;const int N=1e5+10,p=998244353;
int n,x,a[N],dp[N][70]; //dp[i][j]表示到第i个数字为止(不一定以第i个数字结尾),到值为j为止的子序列个数 int main(){ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);cin>>n>>x;for(int i=1;i<=n;i++)	cin>>a[i];//dp初始化,定义是空序列的异或和为0 dp[0][0]=1;for(int i=1;i<=n;i++){for(int j=0;j<70;j++){//状态转移，包括选第i个数和不选第i个数dp[i][j]=(dp[i-1][j^a[i]]+dp[i-1][j])%p;}} cout<<dp[n][x];return 0;
}

数字三角形

学习:
(1)这题跟线性DP的数字三角形有点不一样，多了一个“向左下走的次数与向右下走的次数相差不能超过 1”的要求，所以自底向上dp状态还要加上一个向右走的次数的维度,dp[i][j][k]表示在(i,j)位置向右走了k次的路径最大和(通过最后状态的k得到结果)，最后的状态要对n分奇偶讨论
代码:

#include <bits/stdc++.h>using namespace std;const int N=105;
int n,dp[N][N][55],a[N][N]; //dp[i][j][k]表示在(i,j)位置向右走k次的路径的数字和，相应的向左走的次数为n-i-k int main(){ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);cin>>n;for(int i=1;i<=n;i++){for(int j=1;j<=i;j++){cin>>a[i][j];}}for(int i=n;i>=1;i--){for(int j=1;j<=i;j++){//k从0到n-ifor(int k=0;k<=n-i;k++){//k>=1时，才能向右下走if(k>=1) dp[i][j][k]=a[i][j]+max(dp[i+1][j][k],dp[i+1][j+1][k-1]);//只能向左下走 else dp[i][j][k]=a[i][j]+dp[i+1][j][k];} }}//共走n-1次，分奇偶讨论,保证向左下走的次数与向右下走的次数相差不能超过 1 //n-1为偶数，n为奇数，都一样 if(n%2)	cout<<dp[1][1][(n-1)/2];//n-1为奇数，n为偶数，取最大else cout<<max(dp[1][1][(n-1)/2],dp[1][1][n-1-(n-1)/2]);return 0;
}

(2)
学习:正因为有了"向左下走的次数与向右下走的次数相差不能超过 1"的要求，所有可以归纳出n为奇数最后走到(n,n/2+1)位置，而n为偶数，最后走到(n,n/2)或者(n,n/2+1)位置(结果位置已知)，所有可以直接自顶向下两个维度得到答案，dp[i][j]表示在(i,j)位置的路径最大和(仔细思考和原来题的区别)
代码:

#include <bits/stdc++.h>using namespace std;const int N=105;
int n,dp[N][N],a[N][N]; //dp[i][j]表示在(i,j)位置路径的数字和int main(){ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);cin>>n;for(int i=1;i<=n;i++){for(int j=1;j<=i;j++){cin>>a[i][j];}}//初始化 dp[1][1]=a[1][1];for(int i=2;i<=n;i++){for(int j=1;j<=i;j++){//从上转移到下 dp[i][j]=max(dp[i-1][j],dp[i-1][j-1])+a[i][j]; //是j-1 }} //n为奇数，就一个位置 if(n%2)	cout<<dp[n][n/2+1];else	cout<<max(dp[n][n/2],dp[n][n/2+1]);return 0;
}

LIS(最长上升子序列)

要点:
(1)子序列是指按原顺序选出若干不一定连续的元素的子序列，LIS就是该子序列元素是依次递增的，且长度最大。所以,对于固定的数组，虽然LIS序列不一定唯一，但LIS的长度是唯一的
(2)序列元素a[i]，状态dp[i]表示以a[i]结尾的子序列的长度(包括a[i]),初始状态都为1(自己本身),所以状态转移方程就是i>j,if a[i]>a[j],dp[i]=max(dp[i],dp[j]+1),例如:

id:       1 2 3 4 5 6 7 8
a[i]:     1 3 4 2 5 3 7 2
dp[i]:    1 2 3 2 4 3 5 2
从id转移:默认 1 2 1 3 4 5 1

(3)目前只学O(n^2)的LIS，较难的之后再学

蓝桥勇士

学习:
(1)典型的LIS问题，套模版即可

#include<bits/stdc++.h>using namespace std;const int N=1e3+10;
int n,a[N],dp[N],ans=-1;int main(){ios::sync_with_stdio(false);cin>>n;for(int i=1;i<=n;i++){cin>>a[i];dp[i]=1;}for(int i=2;i<=n;i++){for(int j=1;j<i;j++){//战力值超过则加if(a[i]>a[j])	dp[i]=max(dp[i],dp[j]+1);//选最长的 }ans=max(ans,dp[i]);}cout<<ans;return 0;
}

合唱队形

学习:
(1)结果为左边一个最长子序列，右边一个最长子序列，中间i点截断，所以不妨算dpl和dpr,最终枚举i求得最大值

#include <bits/stdc++.h>using namespace std;const int N=105;
int n,a[N],dpl[N],dpr[N];//dpl为从左向右的LIS,dpr为从右向左的LIS,最终枚举i,使得dpl[i]+dp[r]-1最大即可 int main(){ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);cin>>n;for(int i=1;i<=n;i++){cin>>a[i];dpl[i]=1;dpr[i]=1;}//先算dplfor(int i=2;i<=n;i++){for(int j=1;j<i;j++){if(a[i]>a[j])	dpl[i]=max(dpl[i],dpl[j]+1);}} //再算dprfor(int i=n-1;i>=1;i--){for(int j=n;j>i;j--){if(a[i]>a[j])	dpr[i]=max(dpr[i],dpr[j]+1);}}  //最后枚举i，算最终答案 int ans=-1;for(int i=1;i<=n;i++){ans=max(ans,dpl[i]+dpr[i]-1);//-1是因为i点算了2次 }cout<<n-ans;//ans为合唱队员数量，结果为出列同学数量 return 0;
}

LCS(最长公共子序列)

学习:
(1)求两个序列A，B的最长公共子序列，只有O(n^2)一种解法
(2)状态dp[i][j]为A[1-i],B[1-j](不一定以a[i],b[j]结尾,即公共子序列不一定包括a[i],b[j])时的公共子序列长度,初始值为0,状态转移方程:

if a[i]=b[j] dp[i][j]=dp[i-1][j-1]+1; //相当于把公共元素加入公共子序列，长度加1
else         dp[i][j]=max(dp[i-1],dp[j-1]) //相当于向后遍历但不加入公共子序列，长度取最大的

最终状态就是dp[n][m],例如:

A:1 3 4 2 5
B:1 4 3 6 2
dp:i:0 1 2 3 4 5
j:
0     0 0 0 0 0 0
1     0 1 1 1 1 1
2     0 1 1 2 2 2
3     0 1 2 2 2 2
4     0 1 2 2 2 2
5     0 1 2 2 3 3
最长公共子序列: 1 4 2

(3)求完dp数组，再回过来求最长公共子序列元素的方法:
从(n,m)开始回溯,直到跳出边界停止

if a[i]=b[j] 说明从左上角来，回到(i-1,j-1),得到一个最长公共子序列元素
else 说明是从上方或者左侧最大的方法而来if(dp[i-1][j]>=dp[i][j-1]) 回到(i-1,j)(=默认向上走)else 回到(i,j-1)

最长公共子序列

学习:
(1)模版题
代码:

#include <bits/stdc++.h>
#include <algorithm>using namespace std;const int N=1e3+10;
int n,m,a[N],b[N],dp[N][N];
vector<int> v; //记录最长公共子序列 
int main(){ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);cin>>n>>m;for(int i=1;i<=n;i++)	cin>>a[i];for(int j=1;j<=m;j++)	cin>>b[j];for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){//加入公共子序列 if(a[i]==b[j])	dp[i][j]=dp[i-1][j-1]+1;//不加入 else	dp[i][j]=max(dp[i-1][j],dp[i][j-1]);}}cout<<dp[n][m]<<endl;//打印一个最长公共子序列int i=n,j=m; //起点while(i && j){//是最长公共子序列元素if(a[i]==b[j]){v.emplace_back(a[i]);i=i-1,j=j-1;}//不是else{if(dp[i-1][j]>=dp[i][j-1])	i=i-1;else	j=j-1;} }//反转v,为最长公共子序列元素顺序reverse(v.begin(),v.end());for(auto &x:v){cout<<x<<" ";}return 0;
}

真题

接龙数列

学习:
(1)这题跟最长上升子序列(LIS)类似，只是判断条件不同罢了，记住dp[i]是以a[i]结尾(不是到a[i]为止不包括a[i]那种)，但是只能拿到50分
(2)cin 从标准输入读取的数据最初都是以 字符序列 的形式存在的，具体是什么类型是自己定义转换得来的，所以这题要获得一个数字的首位和尾位，不用写函数对整数操作，直接把数字当做一个字符串输入，提取首位和尾位即可,不过记得减’0’:

string s;
cin>>s;
f[i]=s[0]-'0';
e[i]=s[s.size()-1]-'0';

代码:

#include <bits/stdc++.h>using namespace std;
const int N=1e5+10;
int n,f[N],e[N],dp[N];//f数组记录首位数字，e数组记录末尾数字，dp[i]表示到第i个数字为止(以a[i]为结尾)，最长接龙数列的长度 int main(){ios::sync_with_stdio(false);cin>>n;for(int i=1;i<=n;i++){string s;cin>>s;f[i]=s[0]-'0';e[i]=s[s.size()-1]-'0';dp[i]=1;}int maxn=1;for(int i=2;i<=n;i++){for(int j=1;j<i;j++){//状态转移 if(e[j]==f[i]){dp[i]=max(dp[i],dp[j]+1);}}maxn=max(maxn,dp[i]);}cout<<n-maxn;return 0;
}

优化学习:
(1)因为这题的条件就是把末位数字等与首位数字的两个数字连接起来，本质上就是一个末位数字的状态转移到另一个末位数字的状态,dp[i]表示以i数字结尾的最长接龙数列，因为数字为0-9，所以dp[10]即可，状态转移方程:
dp[b]=max(dp[b],dp[a]+1)(b为第i个数字的末位数字，a为第i个数字的首位数字，即前面某个数字的末位数字)

2023有奖问答

学习:
(1)dp填空题，dp[i][j]表示到第i题为止，到分数j为止的方案数，状态转移方程:

dp[i][0]=dp[i-1][0]+dp[i-1][10]+...+dp[i-1][90]
dp[i][j]=dp[i-1][j-10] //不用+1，因为表示方案数，状态转移过来这是一种方案,j>=10

(2)根据实际意义初始化dp:
dp[1][0]=dp[1][10]=1;//1道题只有0分和10分两种状态
代码:

#include <bits/stdc++.h>using namespace std;
typedef long long ll;
ll dp[35][101];//dp[i][j]表示到第i题为止，到分数j为止的方案数 int main(){ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);//根据实际意义初始化 dp[1][0]=dp[1][10]=1;//1道题只有0分和10分两种状态ll ans=0;for(int i=2;i<=30;i++){//dp[i][0]转移 for(int j=0;j<=90;j+=10){dp[i][0]+=dp[i-1][j];}//dp[i][j]转移for(int j=10;j<=100;j+=10){dp[i][j]=dp[i-1][j-10];//不用+1，因为表示方案数，状态转移过来对于总体来看是一种方案 } }for(int i=1;i<=30;i++){ans+=dp[i][70];}cout<<ans;//ans=8335366return 0;
}

填空题暴力dfs代码:

#include <bits/stdc++.h>using namespace std;
typedef long long ll;
ll ans=0;//x为题目数量，y为分数 
void dfs(int x,int y){//递归中止条件 if(y==100 || x>30)	return;//x>30,x可以=30,此时y可能为70 if(y==70)	ans++;//只要遇到70就加，当做中途放弃dfs(x+1,0);dfs(x+1,y+10); 
}int main(){ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);dfs(0,0);cout<<ans;//ans=8335366return 0;
}

2022积木画

学习:
(1)这题导致状态转移的原因是添加了一次积木(不一定是1个)，而积木又分I型和L型，所以当前状态可以从添加I型积木前的状态1和添加L型积木前的状态2转移过来(类似于爬楼梯)，当前状态又可能出现两行都有积木、第一行积木比第二行多一个、第二行比第一行多一个三种状态(如何想的过程)，所以定义dp[i][j]表示到第i列为止，j=0,1,2分别表示三种状态，的总方案数,状态转移如下图所示
![[积木画.png]]代码:

#include <bits/stdc++.h>using namespace std;
const int N=1e7+10,p=1000000007;
int n,dp[N][3];//dp[i][j]表示到画布第i列为止的方案数,j=0为第一行比第二行多一个,j=1表示两行都一个,j=2表示第二行比第一行多一个 int main(){ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);cin>>n;//先初始化第1列和第2列 dp[1][1]=1,dp[2][0]=dp[2][2]=1,dp[2][1]=2;for(int i=3;i<=n;i++){//核心状态转移，表示添加I型积木或者L型积木转移过来 //dp[i][0],即第i列第一行比第二行多一个dp[i][0]=(dp[i-1][2]+dp[i-2][1])%p;//dp[i][2],和dp[i][0]类似，反过来dp[i][2]=(dp[i-1][0]+dp[i-2][1])%p;//dp[i][1]比较特殊，添加两种类型积木各有两种转移，分类讨论dp[i][1]=( (dp[i-1][1]+dp[i-2][1])%p + (dp[i-1][0]+dp[i-1][2])%p)%p;//三个取余都不能少，位置也不能不对 }cout<<dp[n][1];return 0;
}

李白打酒加强版

学习:
(1)dp问题想好1.状态2.状态转移方程3.什么条件下转移哪些状态(状态的累加)4.最终状态
![[李白打酒加强版1.png]]![[李白打酒加强版2.png]]
所以一共会有三种状态转移，而利用dp[i][j][k]=(dp[i][j][k]+某种状态方案数)%p可以保证方案数是累加的
(2)本题要求最后一次必遇花，就是求dp[n][m-1][1],同时告诉你遍历到m-1,且酒的量不超过m（因为只能减m*1升),且k>=1，因为最后一次要减1
(3)都从0开始遍历，因为要赋只遇店的和只遇花的值，加上条件判断控制状态转移即可，而不是给0赋一些值（自己考虑不周全），并从1开始遍历(错误方法)
代码:

#include <bits/stdc++.h>using namespace std;
const int p=1e9+7;
int n,m,dp[105][105][105];//dp[i][j][k]表示到遇店i次为止，遇花j次为止,酒k升为止的方案次数 int main(){ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);cin>>n>>m;dp[0][0][2]=1;for(int i=0;i<=n;i++){ //必须从0开始，因为i=0或者j=0有很多种情况 for(int j=0;j<=m-1;j++){ //遇花m-1次，最后一次必遇花 for(int k=0;k<=m;k++){ //因为最后要为0，遇花是减1，所以酒的大小不会超过m //遇店 if(i>=1 && k%2==0)	dp[i][j][k]=(dp[i][j][k]+dp[i-1][j][k/2])%p;//遇花(方案累加,加上dp[i][j][k]，如果前面遇店，就等价于加上遇店) if(j>=1 && k>=1)	dp[i][j][k]=(dp[i][j][k]+dp[i][j-1][k+1])%p;  //k>=1,因为最后一次是遇花，k必须大于等于1/*	//等价于下面的方法//遇店 if(i>=1 && k%2==0)	dp[i][j][k]=dp[i-1][j][k/2];//遇花if(j>=1 && k>=1)	dp[i][j][k]=dp[i][j-1][k+1];  //k>=1,因为最后一次是遇花，k必须大于等于1//遇店+遇花if(i>=1 && k%2==0 && j>=1 && k>=1)	dp[i][j][k]=(dp[i-1][j][k/2]+dp[i][j-1][k+1])%p;*/}}}cout<<dp[n][m-1][1];//保证最后一次是花，就是求dp[n][m-1][1] return 0;
}

dfs+记忆化+剪枝:

#include<bits/stdc++.h>
using namespace std;
const int maxn = 100 + 7;
const int mod = 1e9 + 7;
int dp[maxn][maxn][maxn];
int dfs(int x, int y, int z)  // 酒量、遇见店次数、遇见花次数
{if (x < 0 || y < 0 || z < 0) return 0;  // 不合法if (x > z) return 0;  // 酒量不可能大于剩余"遇见花的次数"if (z == 1) return y == 0 && x == 1;  // 最后一次必须遇到的是花 && 酒量只剩1if (dp[x][y][z] != -1) return dp[x][y][z];dp[x][y][z] = (dfs(x * 2, y - 1, z) + dfs(x - 1, y, z - 1)) % mod;return dp[x][y][z];
}
int main()
{memset(dp, -1, sizeof dp);int n, m; cin >> n >> m;cout << dfs(2, n, m) << endl;return 0;
}