怎么用Java實現(xiàn)輸出三角形數(shù)字

這篇文章主要介紹“怎么用Java實現(xiàn)輸出三角形數(shù)字”的相關知識，小編通過實際案例向大家展示操作過程，操作方法簡單快捷，實用性強，希望這篇“怎么用Java實現(xiàn)輸出三角形數(shù)字”文章能幫助大家解決問題。

題目:

給定一個如下圖所示的數(shù)字三角形，從頂部出發(fā)，在每一結點可以選擇移動至其左下方的結點或移動至其右下方的結點，一直走到底層，要求找出一條路徑，使路徑上的數(shù)字的和最大。

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

輸入格式

第一行包含整數(shù) nn，表示數(shù)字三角形的層數(shù)。

接下來 nn 行，每行包含若干整數(shù)，其中第 ii 行表示數(shù)字三角形第 ii 層包含的整數(shù)。

輸出格式

輸出一個整數(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

題解:

         相對于二維數(shù)組來看，每一個數(shù)只能往下放或者右下方走，發(fā)現(xiàn)從下往上走更加方便實現(xiàn)。我們反向思考，從下或者右下方走，如果我們每次都知道了某數(shù)的下放和右下方誰最大了呢?

        每次從最后行的相鄰兩個數(shù)比較誰最大，把每次最大的加到第一個數(shù)的上方，這樣數(shù)組的第一行第一個數(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]);
 
 
 
    }
 
}

關于“怎么用Java實現(xiàn)輸出三角形數(shù)字”的內容就介紹到這里了，感謝大家的閱讀。如果想了解更多行業(yè)相關的知識，可以關注億速云行業(yè)資訊頻道，小編每天都會為大家更新不同的知識點。