P1216 [IOI 1994 / USACO1.5] 数字三角形 Number Triangles——题解

解题思路

令 f[i][j] 表示到达第 $i$ 行第 $j$ 个数时的最大路径和。它只能由上一行第 $j-1$ 个或第 $j$ 个位置到达，因此取两者较大值再加当前数字。答案为最后一行的最大值。

复杂度分析

时间复杂度和空间复杂度均为 $O(r^2)$；可滚动优化到 $O(r)$ 空间。

C++17 参考代码

#include <bits/stdc++.h>
using namespace std;
int f[1005][1005];
int main(){
    ios::sync_with_stdio(false);cin.tie(nullptr);
    int r;cin>>r;
    for(int i=1;i<=r;i++)for(int j=1;j<=i;j++){int x;cin>>x;f[i][j]=max(f[i-1][j-1],f[i-1][j])+x;}
    cout<<*max_element(f[r]+1,f[r]+r+1)<<'\n';return 0;
}

#include <bits/stdc++.h> using namespace std; int f[1005][1005]; int main(){ ios::sync_with_stdio(false);cin.tie(nullptr); int r;cin>>r; for(int i=1;i<=r;i++)for(int j=1;j<=i;j++){int x;cin>>x;f[i][j]=max(f[i-1][j-1],f[i-1][j])+x;} cout<<*max_element(f[r]+1,f[r]+r+1)<<'\n';return 0; }