贴几道记忆化搜索题：
题目链接：
思路：记忆话搜索，不过有一个trick就是如果map[i][j]==0并且不是终点，就直接返回0了。如果map[ i ][ j ]表示跳几格 dp[ i ][ j ] 表示有几种条法 , 其实就是一个子状态继承问题，如果map[ i ][ j ]为k, 那么 dp [ i+k ][ j ] 和dp[i][j+k] 就可以增加 dp[ i ][ j ]种跳跃方法了。
View Code 1 #include2 #include 3 #include 4 using namespace std; 5 typedef long long ll; 6 #define MAXN 44 7 int map[MAXN][MAXN]; 8 char str[MAXN]; 9 ll dp[MAXN][MAXN];10 int n;11 12 ll dfs(int x,int y){13 if(x==n&&y==n){14 return (ll)1;15 }16 if(map[x][y]==0)return 0;17 if(dp[x][y])return dp[x][y];18 for(int flag=0;flag<=1;flag++){19 int xx,yy;20 if(flag){xx=x,yy=y+map[x][y];}21 else {xx=x+map[x][y],yy=y;}22 if(xx>=1&&xx<=n&&yy>=1&&yy<=n){23 dp[x][y]+=dfs(xx,yy);24 }25 }26 return dp[x][y];27 }28 29 30 int main(){31 while(~scanf("%d",&n)&&n!=-1){32 for(int i=1;i<=n;i++){33 scanf("%s",str+1);34 for(int j=1;j<=n;j++){35 map[i][j]=str[j]-'0';36 }37 }38 memset(dp,0,sizeof(dp));39 ll ans=dfs(1,1);40 printf("%I64d\n",ans);41 }42 return 0;43 }
题目链接：
思路：搜索结果取三个方向的最小值即可，最后打印行号比较麻烦，就从头开始找，如果有dp[x][y]==dp[i][y+1]+map[x][y],说明是下一个行号，而i(0-n-1)保证了字典序。
View Code 1 #include2 #include 3 #include 4 using namespace std; 5 #define MAXN 222 6 #define inf 1<<30 7 int map[MAXN][MAXN]; 8 int dp[MAXN][MAXN]; 9 int n,m,len;10 int path[MAXN];11 12 13 int dfs(int x,int y){14 if(dp[x][y]!=inf)return dp[x][y];15 if(y==m-1)return dp[x][y]=map[x][y];16 int ans=min(min(dfs((x-1+n)%n,y+1),dfs(x,y+1)),dfs((x+1)%n,y+1));17 return dp[x][y]=ans+map[x][y];18 }19 20 21 void Solve(int x,int y){22 path[len++]=x;23 if(y==m-1)return ;24 int x1=(x-1+n)%n,x2=x,x3=(x+1)%n;25 for(int i=0;i