dfs记忆化搜索（带限制的选择问题） 讲解：LeetCode打家劫舍|||蓝桥 地宫取宝蓝桥 k进制数剪格子方格分割

dfs记忆化搜索（带限制的选择问题） 讲解：LeetCode打家劫舍||| / 蓝桥 地宫取宝/蓝桥 k进制数//剪格子//方格分割

 记忆化递归的必要性：

普通的递归可能会重复求解某一值，类似斐波那契数列。同样的子问题可能会被求解多次，这样就会很慢很慢很慢

解决方法：我们把历史求解（子问题）记录下来，如果下次需要求解子问题，那么直接取出就好。其时间复杂度为O（1）

例：递归求斐波拉切数

普通递归

int f(int n)
{
	if(n==1)
	{
		return 1;
	}
	if(n==2)
	{
		return 1;
	}
	return f(n-1)+f(n-2);
}

记忆化递归：

（1）参数个数为n，申请一个n维数组（哈希表），确保能够根据参数直接访问数组（哈希表）的值

（2）函数体：

            如果数组（哈希表）已经记录过参数对应的函数值，直接返回该值

            在所有出现return前，return的值记录到数组（哈希表）中

vectornum(1000,-1);
int f1(int n)
{
	if(num[n]!=-1)
	{
		return num[n];
	}
	if(n==1)
	{
		num[1]=1;
		return 1;
	}
	if(n==2)
	{
		num[2]=1;
		return 1;
	}
	num[n]=f(n-1)+f(n-2);
	return num[n];
} 

如果遍历时带限制，用带状态的dfs：

每一步可以有2中选择，要么选，要么不选

   设一个bool型参数flag ,flag=1表示能选，flag=0表示不能选

求解此类问题的模板：

//带限制的选择搜索
//带限制的选择:当前状态选或不选由上一个状态决定
//方法：带状态的dfs+记忆型递归
dp[(set)][]={-1};
 int dfs((set)，int flag)//(set)为不同问题到参数集
{
 if(dp[(set)][flag]!=-1)
 {
   return dp[(set)][flag];
 }
 if()//到终点（规模为1时）
 {
   if(flag)
   {
     dp[(set)][flag]=ans1;
     return ans1;//ans1为能够选择的解
   }
   else
   {
     dp[(set)][flag]=ans2;
     return ans2;//ans2为不能够选择的解
   }
 }
 //输入规模不为1
 if(flag)//能够选择
 { 
   //选择或者不选择都要考虑
   dp[(set)][flag]=ans3;
   return ans3;
 }
 if(!flag)//不能够选择
 {
  //只需考虑不选择
  dp[(set)][flag]=ans4;
  return ans4;
 }
}

 

 

 

 

 

 带状态dfs+记忆化搜索

传入（maxv+1）下标不能有负值

数很大时用longlong

#include
using namespace std;
int n,m,k;
int mat[60][60];
bool check(int x,int y)
{
	return (x>=1&&x<=n&&y>=1&&y<=m);#include
using namespace std;
int n,m,k;
int mat[60][60];
bool check(int x,int y)
{
	return (x>=1&&x<=n&&y>=1&&y<=m);
 } 
 long long dp[60][60][60][15];
 
long long dfs(int x,int y,int maxv,int cnt)
{
	if(dp[x][y][maxv+1][cnt]!=-1)//注意1
	{
		return dp[x][y][maxv+1][cnt];
	}
	if(cnt>k)//如果手里有k+1件宝贝，越界，返回 
	{
		dp[x][y][maxv+1][cnt]=0;
		return 0;
	}
	if(!check(x,y))//越界，修正1 
	{
		dp[x][y][maxv+1][cnt]=0;
		return 0;
	 } 
	if(x==n&&y==m)//到达终点 
	{
		if(mat[x][y]>maxv)//能拿
		{
		   if(cnt==k)//如果手里已经有看件宝贝 
		   {
		   	
		   	dp[x][y][maxv+1][cnt]=1;
		   	return 1;//在终点处选择不拿有一种方案 
		   }
		   else if(cnt==k-1)
		   {
		   	dp[x][y][maxv+1][cnt]=1;
		   	return 1;//在终点处选择拿，有一种方案 
		   }
		   else
		   {
		   	dp[x][y][maxv+1][cnt]=0;
		   	return 0;
		   } 
		}
		else//不能拿 
		{
			if(cnt==k)
			{
				dp[x][y][maxv+1][cnt]=1;
			 return 1;//如果手里已经有k件宝贝，选择不拿，有一种方案
		    } 
			else
			{
				dp[x][y][maxv+1][cnt]=0;
			 return 0; 	
			} 
		} 
	}
	if(mat[x][y]>maxv)
	{
		return dp[x][y][maxv+1][cnt]=dfs(x+1,y,mat[x][y],cnt+1)+dfs(x,y+1,mat[x][y],cnt+1)+dfs(x+1,y,maxv,cnt)+dfs(x,y+1,maxv,cnt);
	}
	else
	{
		return dp[x][y][maxv+1][cnt]=dfs(x+1,y,maxv,cnt)+dfs(x,y+1,maxv,cnt);
	}
}
int main()
{
	cin>>n>>m>>k;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
		{
			cin>>mat[i][j];
		}
	}
	memset(dp,-1,sizeof(dp));//memset的用法
	cout< 
 
 
 
 
 
 
 
 
 
 
记忆化搜索：
 
 
 
 
                          剪格子：
 
 
方格分割：
 
 
 
欢迎分享，转载请注明来源：内存溢出
原文地址:https://54852.com/zaji/5708107.html