AcWing 898. 数字三角形
原题链接
简单
作者:
曦薇
,
2022-04-26 15:51:45
,
所有人可见
,
阅读 102
思路
- 利用动态规划的思想,设前 $i-1$ 层已经找到最大路径,那么对于第 $i$ 层有 $f[i][j]=max(f[i-1][j],f[i-1][j+1])$ 。
- 如果从上向下遍历的话,最后的答案取第 $n$ 层的最大值;如果从下向上遍历的话,结果就为 $num[1][1]$ 。
- 时间复杂度为 $O(N^2)$ ,空间复杂度为 $O(N^2)$ 。
AC代码
#include<bits/stdc++.h>
using namespace std;
const int N=510;
int num[N][N];
int main(void){
int n,i,j;
scanf("%d",&n);
for(i=1;i<=n;i++){
for(j=1;j<=i;j++){
scanf("%d",&num[i][j]);
}
}
for(i=n-1;i>=1;i--){
for(j=1;j<=i;j++){
num[i][j]=max(num[i+1][j],num[i+1][j+1])+num[i][j];
}
}
printf("%d\n",num[1][1]);
return 0;
}