/

1258：【例9.2】数字金字塔_方法二：记忆化搜索

/#include <iostream>#include <algorithm>using namespace std;

const int MAXN = 505;

int A[MAXN][MAXN],F[MAXN][MAXN],N;

int Dfs(int x,int y)

{ if (F[x][y]==-1){ if (x==N) { F[x][y]=A[x][y];cout<<"x0="<<x<<" y="<<y<<" "<<F[x][y]<<endl;}else { F[x][y]=A[x][y]+max(Dfs(x+1,y),Dfs(x+1,y+1));cout<<"x1="<<x<<" y="<<y<<" "<<F[x][y]<<endl;}cout<<"------------------------------"<<endl;

}return F[x][y];

}

int main()

{ freopen("a.in","r",stdin);freopen("b.out","w",stdout);

cin >> N;for(int i = 1;i <= N;i ++)for(int j = 1;j <= i;j ++)    cin >> A[i][j];for(int i = 1;i <= N;i ++)      for(int j = 1;j <= i;j ++)                  F[i][j] = -1;   Dfs(1,1);cout<<"%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%"<
    
     << F[1][1] << endl;fclose(stdin);fclose(stdout);return 0;
    

}

/

由于F[x][y]对于每个合法的(x,y)都只计算过一次，

而且计算是在O(1)内完成的，因此时间复杂度为O(N^2)。

可以通过本题。

/