其实暴力搜索很好想到,但是你就算剪枝剪到极限,也拿不了满分,因为这个题暴搜的时间复杂度是o(2ⁿ),肯定超时了,但是你剪枝剪的好一点就可以拿60的分,但是dfs好想一点在考场上优先选择吧,所以我们先看看dfs是怎么解题的,说来也惭愧这题dp刚开始一直想不对,大概模型是对的,但是有点小细节没处理好,导致结果一直出不来,所以借鉴了下别人的想法,我们先看下这个题给的样例参考代码

想法一:dfs+剪枝+回溯(只能拿一半分,比较好想)

首先的话就是这个题说的遇到花,酒数量减一,遇到店酒的数量翻倍,那么好突破口就再这里,你只需要每次dfs的时候分别讲这两种情况都进行判断就好了,下面我们看一下剪枝怎么剪.

剪枝一:第一中就很简单,超出题目给的店的范围或者花的范围就return;

if(x>N||y>M)                     //如果超出去就剪枝 
{
	return;
}

剪枝二:第二种就是花已经遇见完了但是还有一些店没遇见完,那根据题目所给的意义就是最后一个遇见的必须是花存在矛盾,所以就需要return,还有就是店遇见完了,但是后面的花不足以讲酒喝完那也要return;

if(x<N&&y==M)                      //花遇见完了,但是还有店没有遇见完全就剪枝 
{
	return;
}
if(x==N&&M-y!=k)                  //店遇见完了，但是后面剩的花不足以将酒喝完就剪枝 
{
	return;
}

剪枝三:当我们的酒剩0斗了,但是我们还是遇见了花所以也不行,我们用arr数组存每次遇见的是什么;

if(k==-1&&arr[i-1]==0)           //判断没有酒了但是还是遇见花，这是不合理的 
{
	return;
}

剪枝四:也就是我们的最终条件,花和酒都遇见完全了,并且最后一个也是遇见花了,而且酒也喝完了,我们用flag记录每次的结果.

if(x==N&&y==M&&k==0&&arr[i-1]!=1)      //这里是判断最后一次不能遇到店，只能遇到花// 
{
	flag=(flag+1)%mod;
	return;
}

所以我们看下完整的代码:

#include<stdio.h>
#include<string.h> 
#define mod 1000000007
int N,M,flag=0,k=2,i=1,arr[105];
void dfs(int x,int y)
{
	if(x>N||y>M)                     //如果超出去就剪枝 
	{
		return;
	}
	if(x<N&&y==M)                      //花遇见完了,但是还有店没有遇见完全就剪枝 
	{
		return;
	}
	if(x==N&&M-y!=k)                  //店遇见完了，但是后面剩的花不足以将酒喝完就剪枝 
	{
		return;
	} 
	if(k==-1&&arr[i-1]==0)           //判断没有酒了但是还是遇见花，这是不合理的 
	{
		return;
	}
	if(x==N&&y==M&&k==0&&arr[i-1]!=1)      //这里是判断最后一次不能遇到店，只能遇到花// 
	{
		flag=(flag+1)%mod;
		return;
	}

	arr[i]=0;              //遇到花了 
	k--;
	i++;
	dfs(x,y+1);
	i--;
	k++;

	arr[i]=1;             //遇到店了 
	k*=2;
	i++;
	dfs(x+1,y);
	i--;
	k/=2;
}
int main()
{
	memset(arr,0,sizeof(arr));
	scanf("%d%d",&N,&M);
	dfs(0,0);
	printf("%d",flag%mod);
	return 0;
}

想法二:三维动态规划(满分AC):

我们可以讲这个题看成是一个二维的矩阵,来走方格;

用题目中给的例子,5个店,10个花

向下走我们此时手里面的酒就会翻倍,向右走我们手中的酒就会减一

所以刚开始我们手中的酒就是2然后我们必须保证走到最后一格格子剩下的酒必须是0,而且我们最后一步必须遇到的是花,所以如果只是开二维的话会存在后效性,我们必须开到三维才可以,所以第三维我们记录现在所含有的酒就好了

@:从8那个点开始后面的就不需要算了,因为假如你再遇到店,那么你此时手里面的酒就是16个,你总共的花才10个所以就不可能喝完了,所以我们就直接不用算下面的了

.......:表示不用算了

但是这样算有个不能保证最后一步必须是遇到花了,所以我们从终点往起点走就好了.

所以我们可以写出递推式:

一遇见花了:dp[i][j-1][k-1]+=dp[i][j][k];

二遇见店了:dp[i-1][j][k<<1]+=dp[i][j][k];

#include<stdio.h>
#include<string.h>
#define mod 1000000007
#define max 105
int dp[max][max][max];
int main()
{
	int N,M,flag=0,i,j,k;
	scanf("%d%d",&N,&M);
	memset(dp,0,sizeof(dp));
	dp[N][M][2]=1;            //初始化刚开始手里面是有2斗酒
	for(i=N; i>=0; i--)
	{
		for (j = M; j>=0; j--)
		{
			for (k = M; k>=0; k--)
			{
				if(2*k<=M&&i>=1)
				{
					dp[i-1][j][k<<1]=(dp[i][j][k]+dp[i-1][j][k<<1])%mod;
				}
				if(j>=1&&k>=1)
				{
					dp[i][j-1][k-1]=(dp[i][j-1][k-1]+dp[i][j][k])%mod;	
				}
			}
		}
	}
	printf("%d",dp[0][1][1]%mod);
	return 0;
}

时间复杂度o(NM²)