记忆化DFS 与 基于优先队列的BFS

本文主要是介绍记忆化DFS 与 基于优先队列的BFS，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

Fibonacci 数列的普通DFS实现方式：

int dfs(int n)
{
    if(n==1 || n==2)
        return 1;
    else
        return(dfs(n-1)+dfs(n-2))%1000000007;
}

一、记忆化DFS

Fibonacci 数列的记忆化DFS实现方式：

int dfs(int n)
{
    if(fib[n])
        return fib[n];
    if(n==1 || n==2)
        fib[n]=1;
    else
        fib[n]=(dfs(n-1)+dfs(n-2))%1000000007;
    return fib[n];
}

01背包问题 递归（DFS）实现

int dfs(int i,int v)
{    
    if(i==0 || v<=0)
        return 0;
    if(w[i]>v)
        return dfs(i-1,v);
    else
        return max(dfs(i-1,v),dfs(i-1,v-w[i])+p[i]);
}

记忆化DFS求解01背包问题（基本版）：

int dfs(int i,int v)
{   
    if(dp[i][v]
        return dp[i][v];
    if(i==0 || v<=0)
        return 0;
    if(w[i]>v)
        dp[i][v]=dfs(i-1,v);
    else
        dp[i][v]=max(dfs(i-1,v),dfs(i-1,v-w[i])+p[i]);
    return dp[i][v];
}

我们来看一道例题：

题目链接：Problem - 1078 (hdu.edu.cn)

 解题核心代码

int dfs(int x,int y)
{
	int answer=0;
	if(ans[x][y])
		return ans[x][y];
	for(int i=0;i<4;i++)
		for(int j=i;j<=k;j++)
		{
			int xx=x+dis[i][0]*j;
			int yy=y+dis[i][i]*j;
			if(OK(xx,yy) && init[xx][yy] > init[x][y])
				answer=max(answer,dfs(xx,yy));
		}
	ans[x][y]=answer+init[x][y];
	return ans[x][y];
}

int init[102][102];
int ans[102][102];
int dis[4][2]={0,1,1,0,0,-1,-1,0};
int n,k;

bool OK (int x,int y)
{
	if(x<0 || x>n || y<0 || y>=n)
		return false;
	return true;
}

完整代码：

#include<bits/stdc++.h>
using namespace std;
int n,k;
int init[105][105];
int ans[105][105];
int dis[4][2]={0,1,1,0,0,-1,-1,0};
bool OK(int x,int y){
	if(x<0||x>=n||y<0||y>=n)
		return false;
	return true;
}
int dfs(int x,int y){
	int answer=0;
	if(ans[x][y]) return ans[x][y];
	for(int i=0;i<4;i++){
		for(int j=1;j<=k;j++){
			int xx=x+dis[i][0]*j;
			int yy=y+dis[i][1]*j;
			if(OK(xx,yy)&&init[xx][yy]>init[x][y]){
				answer=max(answer,dfs(xx,yy));
			}
		}
	}
	ans[x][y]=answer+init[x][y];
	return ans[x][y];
}
int main(){
	while(cin>>n>>k){
		if(n==-1 && k==-1) break;
		memset(ans,0,sizeof(ans));
		for(int i=0;i<n;i++){
			for(int j=0;j<n;j++){
				cin>>init[i][j];
			}
		}
		dfs(0,0);
		int mx=0;
		for(int i=0;i<n;i++){
			for(int j=0;j<n;j++){
				if(mx<ans[i][j]) mx=ans[i][j];
			}
		}
		cout<<mx<<endl;
	}
	return 0;
} 

这篇关于记忆化DFS 与 基于优先队列的BFS的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！