Java實(shí)現(xiàn)輸出數(shù)字三角形實(shí)例代碼
題目:
給定一個(gè)如下圖所示的數(shù)字三角形，從頂部出發(fā)，在每一結(jié)點(diǎn)可以選擇移動(dòng)至其左下方的結(jié)點(diǎn)或移動(dòng)至其右下方的結(jié)點(diǎn)，一直走到底層，要求找出一條路徑，使路徑上的數(shù)字的和最大。
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5輸入格式
第一行包含整數(shù) nn，表示數(shù)字三角形的層數(shù)。
接下來(lái) nn 行，每行包含若干整數(shù)，其中第 ii 行表示數(shù)字三角形第 ii 層包含的整數(shù)。
輸出格式
輸出一個(gè)整數(shù)，表示最大的路徑數(shù)字和。
數(shù)據(jù)范圍
1≤n≤5001≤n≤500,
−10000≤三角形中的整數(shù)≤10000−10000≤三角形中的整數(shù)≤10000
輸入樣例：
5 7 3 8 8 1 0 2 7 4 4 4 5 2 6 5
輸出樣例：
30
題解:
相對(duì)于二維數(shù)組來(lái)看，每一個(gè)數(shù)只能往下放或者右下方走，發(fā)現(xiàn)從下往上走更加方便實(shí)現(xiàn)。我們反向思考，從下或者右下方走，如果我們每次都知道了某數(shù)的下放和右下方誰(shuí)最大了呢?
每次從最后行的相鄰兩個(gè)數(shù)比較誰(shuí)最大，把每次最大的加到第一個(gè)數(shù)的上方，這樣數(shù)組的第一行第一個(gè)數(shù)就是最大值了。
例如:
代碼:
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int nums[][] = new int[n][];
for(int i = 0;i<n;i++){
nums[i] = new int[i+1];
for(int j = 0;j<i+1;j++){
nums[i][j] = sc.nextInt();
}
}
for(int i =n-1 ;i>0;i--){
for(int j = 0;j<nums[i].length-1;j++){
nums[i-1][j] += Math.max(nums[i][j],nums[i][j+1]);
}
}
System.out.println(nums[0][0]);
}
}總結(jié)
到此這篇關(guān)于Java實(shí)現(xiàn)輸出三角形實(shí)例代碼的文章就介紹到這了,更多相關(guān)Java輸出三角形內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
相關(guān)文章
Java組件javabean用戶(hù)登錄實(shí)例詳解
這篇文章主要為大家詳細(xì)介紹了Java組件javabean用戶(hù)登錄實(shí)例，內(nèi)容有用戶(hù)登錄，注冊(cè)和退出等，感興趣的小伙伴們可以參考一下2016-05-05
Java的LinkedHashMap的實(shí)現(xiàn)原理詳解
這篇文章主要介紹了Java的LinkedHashMap的實(shí)現(xiàn)原理詳解,???LinkedHashMap是Map接口的哈希表和鏈接列表實(shí)現(xiàn),具有可預(yù)知的迭代順序,此實(shí)現(xiàn)提供所有可選的映射操作,并允許使用null值和null鍵,此類(lèi)不保證映射的順序,特別是它不保證該順序恒久不變,需要的朋友可以參考下2023-09-09
Java大數(shù)字運(yùn)算之BigInteger
在Java中提供了大數(shù)字的操作類(lèi)，即 java.math.BigInteger 類(lèi)與 java.math.BigDecimal 類(lèi)。其中，BigInteger 類(lèi)是針對(duì)大整數(shù)的處理類(lèi),這里有Integer 類(lèi)的解釋?zhuān)褂梅椒ê蛯?shí)例，需要的朋友可以參考下。2017-08-08
簡(jiǎn)單了解Java的默認(rèn)和靜態(tài)方法
這篇文章主要介紹了簡(jiǎn)單了解Java的默認(rèn)和靜態(tài)方法,文中通過(guò)示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友可以參考下2020-01-01
在項(xiàng)目開(kāi)發(fā)中,我們常需要用到加解密算法,本文主要介紹了JAVA各種加密與解密方式匯總,具有一定的參考價(jià)值,感興趣的可以了解一下2023-11-11
Java線(xiàn)程同步問(wèn)題--哲學(xué)家就餐
這篇文章主要介紹了Java線(xiàn)程同步問(wèn)題,線(xiàn)程的同步是保證多線(xiàn)程安全訪(fǎng)問(wèn)競(jìng)爭(zhēng)資源的一種手段。線(xiàn)程的同步是Java多線(xiàn)程編程的難點(diǎn),下面文章舉例的方式講解Java線(xiàn)程同步，具有一定的參考價(jià)值,需要的朋友可以參考下2022-02-02
Java集合框架迭代器Iterator實(shí)現(xiàn)原理解析
這篇文章主要介紹了Java集合框架迭代器Iterator實(shí)現(xiàn)原理解析,文中通過(guò)示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友可以參考下2020-08-08
Java連接數(shù)據(jù)庫(kù)JDBC技術(shù)之prepareStatement的詳細(xì)介紹
這篇文章主要介紹了Java連接數(shù)據(jù)庫(kù)JDBC技術(shù)之prepareStatement的詳細(xì)介紹，文中通過(guò)示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)學(xué)習(xí)吧2020-07-07
JAVA String轉(zhuǎn)化成java.sql.date和java.sql.time方法示例
這篇文章主要給大家分享了關(guān)于JAVA String轉(zhuǎn)化成java.sql.date和java.sql.time的方法，文中給出了詳細(xì)的示例代碼，相信對(duì)大家具有一定的參考價(jià)值，需要的朋友們下面來(lái)一起看看吧。2017-03-03
這篇文章主要介紹了shiro整合swagger需要注意的地方，幫助大家更好的理解和學(xué)習(xí)使用shiro框架，感興趣的朋友可以了解下2021-05-05