package cn.gldwolf.bigdata;/* 3 12 56 23 4 78 34 69 34 19 12 3 54 12 34 *//* 思路：從最底層往上走，判斷下層兩個節點中的最大值， 并將最大值與上層節點中的值相加得到這一步的最大值， 將最大值保存到新的數塔中 再判斷上層節點的的兩個節點的最大值， 再與上上層的節點相加，再保存到新的數塔中， 如此循環往復，最終得到頂層節點的值一定為最大值。輸出路徑時： 將兩個數塔相減，得到下一個節點的值， 下一個節點的值的下標要么和上層節點的下標一致， 要么為上層節點的下標 +1 */import java.util.Scanner;public class NumberTower {public static void main(String[] args) {Scanner input = new Scanner(System.in);System.out.print("Please input the tower height: ");int height = input.nextInt();int firIndex = height - 1; // 數組的長度int[][] orignal = new int[height][]; // 原始的數塔數組int[][] ultima = new int[height][]; // 求最大值以后的數塔數組System.out.println(orignal.length);System.out.println("Please input the number for the number tower: ");// 生成數塔數據for (int i = 0; i < orignal.length; i++) {orignal[i] = new int[i + 1];for (int j = 0; j <= i; j++) {orignal[i][j] = input.nextInt();}}createUltimaArray(firIndex, orignal, ultima);printTrace(firIndex, orignal, ultima);}// 生成求完最大值后的數塔數組public static void createUltimaArray(int firIndex, int[][] orignal, int[][] ultima) {// 將原始數塔中的數據加載到 ultima 數塔中for (int i = 0; i < orignal.length; i++) {ultima[i] = new int[i + 1];for (int j = 0; j <= i; j++) {ultima[i][j] = orignal[i][j];}}// 定義一個臨時變量保存下層節點中兩個值中的最大值int temp_max;// 判斷下層兩個節點中的最大值，并將最大值與節點中的原始數值相加并保存for (int i = firIndex - 1; i >= 0; --i) {for (int j = 0; j <= i; ++j) {temp_max = Math.max(ultima[i + 1][j], ultima[i + 1][j + 1]);ultima[i][j] = temp_max + orignal[i][j];}}}public static void printTrace(int firIndex, int[][] orignal, int[][] ultima) {int max = ultima[0][0];System.out.print(orignal[0][0]); // 第一個節點的值是確定的int j = 0; // 確定初始的二維下標，并提供后續控制 // 這個地方很關鍵// 循環判斷for (int i = 1; i <= firIndex; i++) {// 用 ultima 數組和 orginal 數組相減，得到其子節點在 ultima 數組中的值int node = ultima[i - 1][j] - orignal[i - 1][j];// 因為對上層節點而言，其子節點只有兩個，要么和它下標一致，要么為其下標 +1if (node != ultima[i][j]) // 判斷，如果和它相同的下標不對，則對下層的下標 +1++j;System.out.print(" --> " + orignal[i][j]);}} }

總結

以上是生活随笔為你收集整理的动态规划算法之数塔问题的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。