欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

数字三角形最长路径

程序员文章站 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);
}
相关标签: # C++编程