算法设计与分析: 3-7 数字三角形问题

d3y1

于 2018-07-12 13:33:10 发布

阅读量2.2k

点赞数 1

分类专栏： Algorithm 动态规划计算机算法设计与分析 Java 计算机算法设计与分析文章标签：数字三角形问题动态规划算法 Java

本文链接：https://blog.csdn.net/IOIO_/article/details/81014150

版权

本文探讨了数字三角形问题，旨在找到从顶到底的路径，使得路径经过的数字之和最大。问题描述中提到，每一步只能从当前数走到下一行的左侧或右侧相邻数字。提供了一个Java实现的输入输出示例，并引用了王晓东《计算机算法设计与分析》（第3版）的相关内容。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

3-7 数字三角形问题

问题描述

给定一个由n行数字组成的数字三角形，如下图所示：

试设计一个算法，计算出从三角形的顶至底的一条路径，使该路径经过的数字总和最大（每一步只能从一个数走到下一层上和它最近的左边的数或者右边的数）。

输入数据：
第一行是数字三角形的行数，接下来 n 行是数字三角形中的数字。

Java

import java.util.Scanner;

public class ShuZiSanJiaoXing {
   

    public static void main(String[] args){
        Scanner input = new Scanner(System.in);

最低0.47元/天解锁文章