记忆化搜索-poj1088、poj1579、poj1163

poj1088 滑雪

分析：经典的记忆化搜索，很容易想到用dfs,但是，如果对每一个点都进行dfs，那么就会超时，这里可以利用记忆化搜索，实际就是对dfs的一点剪枝，对于当前的点的搜索，利用前面的点的搜索结果来更新本点出发能下滑的最长距离即可

#include
  
   
#include
   
     #define MAX 101 int R,C; int map[MAX][MAX]; int flag[MAX][MAX]; void Input() { int i,j; memset(flag,0,sizeof(flag)); for(i=0;i
    
     0)return flag[x][y]; for(int i=0;i<4;i++) { int a=x+vis[i][0],b=vis[i][1]+y; if(a>=0 && b>=0 && a
     
      map[a][b]) { int t=dfs(a,b); if(max
      
       poj1579
       
 
       
按照题意构造dfs函数，并且用记忆化搜索(就是标记)
 
       






       
#include
        
         
#include
         
           int flag[21][21][21]; int w(int a,int b,int c) { if(a<=0 || b<=0 ||c<=0) return 1; if(a>20 || b>20 || c>20) return w(20,20,20); else if(a
          
 poj1163 数字三角形
 
经典的记忆化搜索
 
#include
            
             
#include
             
               int N; int map[101][101]; int dp[101][101]; int dfs(int x,int y) { if(x==N) return map[x][y]; if(dp[x][y]>0) return dp[x][y]; int a=dfs(x+1,y); int b=dfs(x+1,y+1); if(a>b) dp[x][y]=map[x][y]+a; //记忆化标记 else dp[x][y]=map[x][y]+b; return dp[x][y]; /* 等价 if(dp[x][y]>0) return dp[x][y]; return dp[x][y]=a[x][y]+(x==N  0:(dfs(x+1,y)>dfs(x+1,y+1)   dfs(x+1,y):dfs(x+1,y+1)) ); */ } int main() { int i,j; while(~scanf("%d",&N)) { memset(dp,0,sizeof(dp)); for(i=1;i<=N;i++) for(j=1;j<=i;j++) scanf("%d",&map[i][j]); printf("%d\n",dfs(1,1)); } return 0; }