题目描述

打印输出路径的方法

样例

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

const int N = 510;
int n;
int s[N][N];
int f[N][N];
int g[N][N];
int main()
{
    cin>>n;
    for(int i = 1; i <= n; i ++)
        for(int j = 1; j <= i; j ++)
            {
                cin>>s[i][j];
                f[i][j] = s[i][j];
            }

    for(int i = n - 1; i >= 1; i --)
        for(int j = 1; j <= i; j ++)
            s[i][j] = max(s[i + 1][j], s[i + 1][j + 1]) + s[i][j];

    int q = 1,m = 2; 
    int c[n + 1];c[1] = f[1][1];
    cout<<c[1]<<"  ";
    for(int i = 2; i <=n; i ++)
    {
     if(s[m][q] > s[m][q + 1])
     {
         c[i] = f[m][q];
         q = q;
         m ++;
     }
     else
     {
         c[i] = f[m][q + 1];
         q = q + 1;
         m++;
     }
     cout<<c[i]<<"  ";
    }

    cout<<s[1][1]<<endl;
    return 0;
}

算法1

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla