poj 1163

http://poj.org/problem?id=1163

以我的理解，他们这是对递归的重计算问题的优化，从而演变成的另一种算法；

一般只能计算最大或最小问题；

一下是我的代码；

前一个是递归；

后一个是动态规划；

#include<stdio.h>
 #include<stdlib.h>
 #include<string.h>
 #include<math.h>
 #include<iostream>
 #include<algorithm>
 using namespace std;


 const int sizen=150;
 int a[sizen][sizen];
 int mat[150][150];
 int n;


 int Max(int i,int j)
 {
     if(i==n)
         return mat[i][j];
     else
     {
         if(a[i][j]!=-1)
             return a[i][j];
         int x=Max(i+1,j);
         int y=Max(i+1,j+1);
         a[i][j]=max(x,y)+mat[i][j];
         return a[i][j];
     }
 }


 int main()
 {
     int i,j;
     while(scanf("%d",&n)!=EOF)
     {
         memset(a,-1,sizeof(a));
         memset(mat,0,sizeof(mat));
         for(i=1;i<=n;i++)
             for(j=1;j<=i;j++)
                 scanf("%d",&mat[i][j]);
         printf("%d\n",Max(1,1));
     }
     return 0;
 }
 #include<stdio.h>
 #include<stdlib.h>
 #include<string.h>
 #include<math.h>
 #include<algorithm>
 #include<iostream>
 using namespace std;


 const int sizen=150;
 int arr[sizen];
 int mat[sizen][sizen];


 int main()
 {
     int n;
     int i,j;
     while(scanf("%d",&n)!=EOF)
     {
         memset(arr,0,sizeof(arr));
         for(i=1;i<=n;i++)
             for(j=1;j<=i;j++)
                 scanf("%d",&mat[i][j]);
         for(i=n;i>=1;i--)
             for(j=1;j<=i;j++)
                 arr[j]=mat[i][j]+max(arr[j],arr[j+1]);
         printf("%d\n",arr[1]);
     }
     return 0;
 }