Hrbust 1812 http://acm.hrbust.edu.cn/index.php?m=ProblemSet&a=showProblem&problem_id=1812
有两种方法，一种是从a[0][0]向后面推导，一种是从a[n-1][n-1]向前面推到，思想都是一样的
从后往前推导
1 #include<stdio.h> 2 #include<iostream> 3 #include<algorithm> 4 #include<string.h> 5 using namespace std; 6 int dp[1005][1005]; 7 int a[1005][1005]; 8 int n; 9 int Minlen(int i,int j) 10 {if(dp[i][j]!=-1)return dp[i][j]; 11 if(i==n-1&&j==n-1)return dp[i][j]=a[i][j]; 12 if(j==n-1)return dp[i][j]=a[i][j]+Minlen(i+1,j); 13 if(i==n-1)return dp[i][j]=a[i][j]+Minlen(i,j+1); 14 return dp[i][j]=a[i][j]+min(Minlen(i+1,j),Minlen(i,j+1)); 15 16 } 17 int main() 18 { 19 while(cin>>n){ 20 memset(dp,-1,sizeof(dp)); 21 memset(a,0,sizeof(a)); 22 for(int i=0;i<n;i++){ 23 for(int j=0;j<n;j++){ 24 cin>>a[i][j]; 25 } 26 } 27 cout<<Minlen(0,0)<<endl; 28 } 29 }
从前往后面推导
1 #include<stdio.h> 2 #include<iostream> 3 #include<algorithm> 4 #include<string.h> 5 using namespace std; 6 int a[105][1005]; 7 int main() 8 { 9 int n; 10 while(cin>>n) 11 {memset(a,0,sizeof(a)); 12 for(int i=0;i<n;i++) 13 { 14 for(int j=0;j<n;j++) 15 { 16 cin>>a[i][j]; 17 if(i==0&&j!=0)a[i][j]+=a[0][j-1]; 18 else if(i!=0&&j==0)a[i][j]+=a[i-1][0]; 19 else if(i!=0&&j!=0)a[i][j]+=(min(a[i-1][j],a[i][j-1])); 20 } 21 } 22 cout<<a[n-1][n-1]<<endl; 23 } 24 }