题目：http://www.lightoj.com/volume_showproblem.php?problem=1004
题意：给定一个由数字组成的菱形，问从顶端走到底端的路线上数字的最大和，行走方式为可以从当前数字向下一层临近的两个数字走。
思路：动态规划。对于菱形的上半部，可以得状态转移方程为dp[i][j] += max(dp[i-1][j-1], dp[i-1][j])，对于下半部，可以得状态转移方程为dp[i][j] = max(dp[i-1][j], dp[i-1][j+1])，最后dp[2*n-1][1]就是答案
但是我非常想用dfs写！：
先来个错误代码：
#include<iostream> #include<cstdio> #include<algorithm> #include<cstring> #include<sstream> using namespace std; int mp[210][210],num=0,n,vis[210][210]; int nx[][2]= {1,0,1,1}; int ny[][2]= {1,-1,1,0}; int dfs(int x,int y) { int i,tx,ty; if(vis[x][y]!=0) return vis[x][y]; if(x==2*n-1) return mp[x][y]; if(x<=n-1) { for(i=0; i<2; i++) { tx=x+nx[i][0]; ty=y+nx[i][1]; if(mp[tx][ty]==0) continue; vis[tx][ty]=max(vis[tx][ty],dfs(tx,ty));//tx,ty会变，x,y这个点下方的左右两点根本没比较 } vis[x][y]=mp[x][y]+vis[tx][ty]; } else if(x>=n) { for(i=0; i<2; i++) { tx=x+ny[i][0]; ty=y+ny[i][1]; if(mp[tx][ty]==0) continue; vis[tx][ty]=max(vis[tx][ty],dfs(tx,ty)); } vis[x][y]=mp[x][y]+vis[tx][ty]; } return vis[x][y]; } int main() { int t,i,j,ss=1; cin>>t; while(t--) { num=0; memset(mp,0,sizeof(mp)); memset(vis,0,sizeof(vis)); scanf("%d",&n); for(i=1; i<=n; i++) for(j=1; j<=i; j++) scanf("%d",&mp[i][j]); for(i=n+1; i<=2*n-1; i++) for(j=1; j<=2*n-i; j++) scanf("%d",&mp[i][j]); num=dfs(1,1); printf("Case %d: %d\n",ss++,num); } return 0; }改正代码： #include<iostream> #include<cstdio> #include<algorithm> #include<cstring> #include<sstream> using namespace std; int mp[210][210],num=0,n,vis[210][210]; int nx[][2]= {1,0,1,1}; int ny[][2]= {1,-1,1,0}; int dfs(int x,int y) { int tx,ty,i; if(vis[x][y]!=0) return vis[x][y]; if(x==2*n-1&&y==1) { return mp[x][y]; } if(x<=n-1) { for(i=0; i<2; i++) { tx=x+nx[i][0]; ty=y+nx[i][1]; if(mp[tx][ty]==0) continue; vis[x][y]=max(vis[x][y],mp[x][y]+dfs(tx,ty)); } } else if(x>=n) { for(i=0; i<2; i++) { tx=x+ny[i][0]; ty=y+ny[i][1]; if(mp[tx][ty]==0) continue; vis[x][y]=max(vis[x][y],mp[x][y]+dfs(tx,ty)); } } return vis[x][y]; } int main() { int t,i,j,ss=1; cin>>t; while(t--) { num=0; memset(mp,0,sizeof(mp)); memset(vis,0,sizeof(vis)); scanf("%d",&n); for(i=1; i<=n; i++) for(j=1; j<=i; j++) scanf("%d",&mp[i][j]); for(i=n+1; i<=2*n-1; i++) for(j=1; j<=2*n-i; j++) scanf("%d",&mp[i][j]); num=dfs(1,1); printf("Case %d: %d\n",ss++,num); } return 0; }再来个超时代码：
#include<iostream> #include<cstdio> #include<algorithm> #include<cstring> #include<sstream> using namespace std; int mp[210][210],num=0,n,vis[210][210]; int nx[][2]= {1,0,1,1}; int ny[][2]= {1,-1,1,0}; int dfs(int x,int y) { if(x==2*n-1) return vis[x][y]=mp[x][y]; if(vis[x][y]>0) return vis[x][y]; if(x<n) return vis[x][y]=mp[x][y]+max(dfs(x+1,y),dfs(x+1,y+1)); else if(x<2*n-1&&x>=n) { if(y>1) return vis[x][y]=mp[x][y]+max(dfs(x+1,y),dfs(x+1,y-1));//会一直向下扩展，类似矩形剪去一个角，导致超时 else return vis[x][y]=mp[x][y]+dfs(x+1,y); } } int main() { int t,i,j,ss=1; cin>>t; while(t--) { num=0; memset(mp,0,sizeof(mp)); memset(vis,0,sizeof(vis)); scanf("%d",&n); for(i=1; i<=n; i++) for(j=1; j<=i; j++) scanf("%d",&mp[i][j]); for(i=n+1; i<=2*n-1; i++) for(j=1; j<=2*n-i; j++) scanf("%d",&mp[i][j]); num=dfs(1,1); printf("Case %d: %d\n",ss++,num); } return 0; }改正代码：
#include<iostream> #include<cstdio> #include<algorithm> #include<cstring> #include<sstream> using namespace std; int mp[210][210],num=0,n,vis[210][210]; int nx[][2]= {1,0,1,1}; int ny[][2]= {1,-1,1,0}; int dfs(int x,int y) { if(x==2*n-1) return vis[x][y]=mp[x][y]; if(vis[x][y]>0) return vis[x][y]; if(x<n) return vis[x][y]=mp[x][y]+max(dfs(x+1,y),dfs(x+1,y+1)); else if(x<2*n-1&&x>=n) { if(y==1) return vis[x][y]=mp[x][y]+dfs(x+1,y); else if(y==2*n-x) return vis[x][y]=mp[x][y]+dfs(x+1,y-1); else return vis[x][y]=mp[x][y]+max(dfs(x+1,y),dfs(x+1,y-1)); } } int main() { int t,i,j,ss=1; cin>>t; while(t--) { num=0; memset(mp,0,sizeof(mp)); memset(vis,0,sizeof(vis)); scanf("%d",&n); for(i=1; i<=n; i++) for(j=1; j<=i; j++) scanf("%d",&mp[i][j]); for(i=n+1; i<=2*n-1; i++) for(j=1; j<=2*n-i; j++) scanf("%d",&mp[i][j]); num=dfs(1,1); printf("Case %d: %d\n",ss++,num); } return 0; } 学习就是不断纠错的过程，加油！