数字三角形最长路径
程序员文章站
2024-02-21 14:31:46
...
数字三角形最长路径问题就是在如图所示的三角形中,由上至下,寻找一条路径使得经过所有路径之后,所得数值最大。
输入样例:
第一行是三角形的行数n
以下n行都是三角形各行数据
3
1
2 3
5 3 6
输出:
10
递推方法
# include<iostream>
#include<algorithm>
using namespace std;
#define MAX 100
int n,D[MAX][MAX];
int maxPath(int i,int j)
{
if(i == n)
return D[i][j];
else
{
return max(maxPath(i+1,j),maxPath(i+1,j+1)) + D[i][j];
}
}
int main()
{
freopen("1.txt","r",stdin);
freopen("2.txt","w",stdout);
cin >>n;
for(int i = 1;i <= n;i++)
for(int j = 1;j <= i;j++)
cin >> D[i][j];
cout << maxPath(1,1);
}
这种方法可行,但是算法复杂度过大,在样例超过一定规模会TLE
原因是重复计算!!!
记忆递推式动态规划
将每次计算出的结点最大路径值记录在数组中,避免重复运算
# include<iostream>
#include<algorithm>
using namespace std;
#define MAX 100
int n,D[MAX][MAX],maxData[MAX][MAX];
int maxPath(int i,int j)
{
if(maxData[i][j] != -1)
return maxData[i][j];
else if(i == n)
{
maxData[i][j] = D[i][j];
return maxData[i][j];
}
else
{
maxData[i][j] = max(maxPath(i+1,j),maxPath(i+1,j+1)) + D[i][j];
return maxData[i][j];
}
}
int main()
{
freopen("1.txt","r",stdin);
freopen("2.txt","w",stdout);
cin >>n;
for(int i = 1;i <= n;i++)
for(int j = 1;j <= i;j++)
{
cin >> D[i][j];
maxData[i][j] = -1;
}
cout << maxPath(1,1);
}