DP走方格型

Hrbust 1812  http://acm.hrbust.edu.cn/index.php?m=ProblemSet&a=showProblem&problem_id=1812

有两种方法，一种是从a[0][0]向后面推导，一种是从a[n-1][n-1]向前面推到，思想都是一样的

从后往前推导

 #include<stdio.h>

 #include<iostream>

 #include<algorithm>

 #include<string.h>

 using namespace std;

 int dp[][];

 int a[][];

 int n;

 int Minlen(int i,int j)

 {if(dp[i][j]!=-)return dp[i][j];

      if(i==n-&&j==n-)return dp[i][j]=a[i][j];

  if(j==n-)return dp[i][j]=a[i][j]+Minlen(i+,j);

  if(i==n-)return dp[i][j]=a[i][j]+Minlen(i,j+);

 return  dp[i][j]=a[i][j]+min(Minlen(i+,j),Minlen(i,j+));

 }

 int main()

 {

     while(cin>>n){

         memset(dp,-,sizeof(dp));

         memset(a,,sizeof(a));

         for(int i=;i<n;i++){

             for(int j=;j<n;j++){

                 cin>>a[i][j];

             }

         }

         cout<<Minlen(,)<<endl;

     }

 }

从前往后面推导

 #include<stdio.h>

 #include<iostream>

 #include<algorithm>

 #include<string.h>

 using namespace std;

 int a[][];

 int main()

 {

     int n;

     while(cin>>n)

     {memset(a,,sizeof(a));

         for(int i=;i<n;i++)

         {

             for(int j=;j<n;j++)

             {

                 cin>>a[i][j];

                 if(i==&&j!=)a[i][j]+=a[][j-];

                 else if(i!=&&j==)a[i][j]+=a[i-][];

                 else if(i!=&&j!=)a[i][j]+=(min(a[i-][j],a[i][j-]));

             }

         }

        cout<<a[n-][n-]<<endl;

     }

 }