POJ 1163 The Triangle

素颜马尾好姑娘i 2022-06-10 12:44 147阅读 0赞

**Description**

7
    3   8
    8   1   0
    2   7   4   4
    4   5   2   6   5
    
    (Figure 1)

Figure 1 shows a number triangle. Write a program that calculates the highest sum of numbers passed on a route that starts at the top and ends somewhere on the base. Each step can go either diagonally down to the left or diagonally down to the right.

**Input**

Your program is to read from standard input. The first line contains one integer N: the number of rows in the triangle. The following N lines describe the data of the triangle. The number of rows in the triangle is > 1 but <= 100. The numbers in the triangle, all integers, are between 0 and 99.

**Output**

Your program is to write to standard output. The highest sum is written as an integer.

**Sample Input**

5
    7
    3 8
    8 1 0 
    2 7 4 4
    4 5 2 6 5

**Sample Output**

30

**Code**

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

发表评论取消回复

表情：

评论列表（有 0 条评论，147人围观）

还没有评论，来说两句吧...

相关阅读

相关 ACM学习-POJ-1163-The Triangle

菜鸟学习ACM，纪录自己成长过程中的点滴。学习的路上，与君共勉。 ACM学习-POJ-1163-The Triangle <table style="font-wei

桃扇骨/ 2022年09月17日 06:24/ 0 赞/ 158 阅读

相关 DP 数字三角形(POJ1163)

7 3 8 8 1 0 2 7 4 4 4 5 2 6 5 在上面的数字三角形中寻找一条从顶部到底边的路径，使得路径上所经过的数字之和最大。路径上的每一步都只能往

朱雀/ 2022年08月18日 02:36/ 0 赞/ 5 阅读

相关 POJ 2079 Triangle（旋转卡壳）

POJ 2079 Triangle（旋转卡壳）：[http://poj.org/problem?id=2079][http_poj.org_problem_id_2079]

比眉伴天荒/ 2022年07月24日 11:18/ 0 赞/ 185 阅读

相关 POJ 3176-Cow Bowling/POJ 1163-The Triangle（简单DP-数塔）

Cow Bowling <table> <tbody> <tr> <td><strong>Time Limit:</strong> 1000MS<

冷不防/ 2022年07月12日 13:28/ 0 赞/ 139 阅读

相关 poj1163

include <iostream> include <algorithm> using namespace std;

曾经终败给现在/ 2022年06月18日 04:20/ 0 赞/ 195 阅读

相关 poj1163 递归或dp

递归的版本：很可惜tle了。 package p1163; import java.io.File; import java.io.File

红太狼/ 2022年06月13日 10:51/ 0 赞/ 185 阅读

相关 POJ 1163 The Triangle

Description 7 3 8 8 1 0 2 7 4 4 4 5 2 6 5

素颜马尾好姑娘i/ 2022年06月10日 12:44/ 0 赞/ 148 阅读

相关旋转卡壳入门三——POJ 2079 Triangle

[Triangle][] Given n distinct points on a plane, your task is to find the triangle tha

我会带着你远行/ 2022年05月24日 05:12/ 0 赞/ 221 阅读

相关 POJ 1471Triangles

Triangles <table> <tbody> <tr> <td><strong>Time Limit:</strong> 1000MS</t

古城微笑少年丶/ 2022年05月16日 04:47/ 0 赞/ 164 阅读

相关 The Triangle POJ - 1163 (动态规划经典入门题)

7 3 8 8 1 0 2 7 4 4 4 5 2 6 5 (Figure 1

刺骨的言语ヽ痛彻心扉/ 2022年04月23日 15:16/ 0 赞/ 171 阅读