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;
}