本人小白但是最近学习了动态规划的记忆化搜索算法，就是经典的那道数字三角形的题，题目中最后说的只是要显示最大路径的值（就是求和），没说要求走过的点的坐标，我想顺便输出坐标，有没有什么高效的算法？我目前想出来一种（效率可能很低），就是用一开始记录到底的值的数组d来求，遍历每一行的d，求其的最大值然后记录下坐标。但是我觉得可以通过边搜边记录边筛的方式来弄。

一下是我尝试后者的代码

#include<iostream>

#include<algorithm>

using namespace std;

int d[107][107],a[107][107],n,njc,Roadx[100],Roady[100],Road_jc=1;

void PrintRoad(){

for(int i=1;i<=Road_jc;i++){

cout<<"第"<<i<<"组是"<<"("<<Roadx[i]<<","<<Roady[i]<<")"<<endl;

}

}

void Get_Road(int a,int b){

Roadx[Road_jc]=a;

Roady[Road_jc]=b;

Road_jc++;

}

void Get_Putin(){

for(int wjc=1;wjc<=n;wjc++){

njc=1;

for(int njc=1;njc<=wjc;njc++){

cin>>a[wjc][njc];

d[wjc][njc]=0;

}

}

}

int dfs(int x,int y){

if(d[x][y]!=0){

return d[x][y];

}

if(d[x][y]==0){

d[x][y]=a[x][y]+max(dfs(x+1,y),dfs(x+1,y+1));

if(dfs(x+1,y)>=dfs(x+1,y+1))Get_Road(x+1,y);

else Get_Road(x+1,y+1);

return d[x][y];

}

}

void Start_Chu(){

for(int jc=1;jc<=n;jc++)d[n][jc]=a[n][jc];

}

void De_Bug(){

for(int wjc=1;wjc<=n;wjc++){

njc=1;

for(int njc=1;njc<=wjc;njc++){

cout<<"a["<<wjc<<"]"<<"["<<njc<<"]"<<a[wjc][njc]<<" ";

cout<<"d["<<wjc<<"]"<<"["<<njc<<"]"<<d[wjc][njc]<<" ";

cout<<endl;

}

}

}

int main(){

cin>>n;

Get_Putin();

Start_Chu();

cout<<dfs(1,1)<<endl;

PrintRoad();

system("pause");

return 0;

}