算法1
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
// 思路:从上往下遍历,f(i, j)表示从顶点到点(i, j)的所有路径中的最大数字和
#include <iostream>
using namespace std;
const int N = 510, INF = 0x3f3f3f3f;
int n, a[N][N];
int f[N][N];
int main()
{
scanf("%d", &n);
for (int i = 1; i <= n; i ++ )
for (int j = 1; j <= i; j ++ )
scanf("%d", &a[i][j]);
// 每一层的第0个数和第i+1个数的数字和也需要初始化
for (int i = 0; i <= n; i ++ )
for (int j = 0; j <= i + 1; j ++ )
f[i][j] = -INF;
f[1][1] = a[1][1]; // 顶点一定加入结果中
for (int i = 2; i <= n; i ++ ) // 从第2层开始搜索
for (int j = 1; j <= i; j ++ )
f[i][j] = max(f[i - 1][j - 1] + a[i][j], f[i - 1][j] + a[i][j]);
int res = -INF;
for (int i = 1; i <= n; i ++ ) res = max(res, f[n][i]); // 取最后一层中最大数字和的路径
printf("%d\n", res);
return 0;
}
算法2
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla