本文共 1517 字，大约阅读时间需要 5 分钟。

为了解决这个问题，我们需要找到从顶部到底边的路径，使得路径上所经过的数字之和最大。路径只能向左下方或右下方移动。我们可以使用动态规划的方法来解决这个问题。

方法思路

解决代码

import static java.lang.Math.max;public class Main {    static int n;    static int[][] triangle;    static int ans = 0;    public static void main(String[] args) {        Scanner sc = new Scanner(System.in);        n = sc.nextInt();        triangle = new int[n][];        for (int i = 0; i < n; i++) {            triangle[i] = new int[i + 1];            for (int j = 0; j <= i; j++) {                triangle[i][j] = sc.nextInt();            }        }        if (n > 1) {            int[] dp = new int[n];            dp[0] = triangle[0][0];            for (int i = 1; i < n; i++) {                for (int j = 1; j <= i; j++) {                    dp[j] = max(dp[j - 1], dp[j]) + triangle[i][j];                }            }            ans = dp[n - 1];            System.out.println(ans);        } else {            System.out.println(triangle[0][0]);        }        sc.close();    }}

代码解释

这个方法通过动态规划有效地解决了问题，确保了时间和空间复杂度的优化。

转载地址：http://gvwg.baihongyu.com/