专栏首页AI那点小事算法训练 数字三角形

算法训练 数字三角形

问题描述   (图3.1-1)示出了一个数字三角形。 请编一个程序计算从顶至底的某处的一条路   径,使该路径所经过的数字的总和最大。   ●每一步可沿左斜线向下或右斜线向下走;   ●1<三角形行数≤100;   ●三角形中的数字为整数0,1,…99;

  .   (图3.1-1) 输入格式   文件中首先读到的是三角形的行数。

  接下来描述整个三角形 输出格式   最大总和(整数) 样例输入 5 7 3 8 8 1 0 2 7 4 4 4 5 2 6 5 样例输出 30


代码如下:

import java.util.Scanner;

public class Main {
    static int[][] D = new int[101][101];
    static int N;

    public static int MaxSum(){
        for ( int i1 = N-1 ; i1 >= 1 ; i1--){
            for ( int j1 = 1 ; j1 <= i1 ; j1++){
                D[N][j1] = max(D[N][j1],D[N][j1+1]) + D[i1][j1];
            }
        }
        return D[N][1];
    }

    public static int max(int a , int b){
        return (a > b)?a:b;
    }

    public static void main(String[] args) {
        // TODO Auto-generated method stub
        Scanner in = new Scanner(System.in);
        N = in.nextInt();
        for ( int i = 1 ; i <= N ; i++){
            for ( int j = 1 ; j <= i ; j++){
                D[i][j] = in.nextInt();
            }
        }
        System.out.print(MaxSum());
        in.close();
    }

}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • CCF考试——201403-1相反数

    有 N 个非零且各不相同的整数。请你编一个程序求出它们中有多少对相反数(a 和 -a 为一对相反数)。

    AI那点小事
  • 剑指offer——数组中只出现一次的数字

    题目描述 一个整型数组里除了两个数字之外,其他的数字都出现了偶数次。请写程序找出这两个只出现一次的数字。

    AI那点小事
  • 创造新世界

    众所周知计算机代码底层计算都是0和1的计算,牛牛知道这点之后就想使用0和1创造一个新世界!牛牛现在手里有n个0和m个1,给出牛牛可以创造的x种物品,每种物品都由...

    AI那点小事
  • 微信小程序--基于ColorUI构建皮皮虾短视频去水印组件(仅供学习使用)

    没错,我是皮友,我想学习舞蹈(/doge)和瑜伽 ,要无水印的那种有助于我加深学习。

    Kindear
  • 前端-微信小程序开发(3):这是一个组件

    之前这个组件是一个容器类组件,弹出层可设置载入的html结构,然后再设置各种事件即可,这种组件有一个特点:

    grain先森
  • uniapp图片弹框效果

    需求:点击提交按钮,提交成功后会弹出一个弹框,提示成功,点击右上角的叉号或者我知道了,隐藏弹框效果。

    王小婷
  • View事件分发、滑动冲突 详解

    3)view的处理过程:主要是onTouchListener、OnTouchEvent、onClick的关系

    胡飞洋
  • 16.普通用户、网格长、网格员,操作数据(3)newapp/components/putong.vue

    玩蛇的胖纸
  • Dalvik虚拟机原理及Xposed hook原理

    这块知识本身是挺多的,网上有对应的源码分析,本文尽量从不分析代码的角度来把原理阐述清楚。

    用户2930595
  • 5-VI--ListView事件全解析

    张风捷特烈

扫码关注云+社区

领取腾讯云代金券