AcWing 898. 数字三角形
原题链接
简单
作者:
季之秋
,
2021-02-09 17:08:47
,
所有人可见
,
阅读 295
/*
核心:从起点到任一点的路径和max拆分成到这个点的两条路径f[i-1][j]和f[i-1][j-1]求一个max
考虑一下i和j的的取值范围和f[0][0]或f[1][1]的状态
很像数学归纳法,我们只要得到最初状态的值和到下一个状态的值,就可以求出任一状态的值
逆序核心:因为是最后一层到第一点的最大路径和 f[i][j] 拆分成f[i+1][j]和f[i+1][j+1]求一个max
最后一层的f值就是自己所以只要一个数组,然后用最后一层求出n-1层的最大值、如此反复
就是f[i][j]看成最后一层到这个点的最大路径和的一个表示
*/
import java.util.*;
public class Main{
public static void main(String[] args){
Scanner sc=new Scanner(System.in);
int n=sc.nextInt();
int N=510;
int f[][]=new int[N][N];
for(int i=1;i<=n;i++){
for(int j=1;j<=i;j++){
f[i][j]=sc.nextInt();
}
}
for(int i=n-1;i>=0;i--){
for(int j=1;j<=i;j++){
f[i][j]+=Math.max(f[i+1][j],f[i+1][j+1]);
}
}
System.out.println(f[1][1]);
}
}