數字三角形

來自專欄 Java之鏈

如圖，該三角形第一行有一個非負數字，除了最後一行外，每個數字的左下方和右下方各有一個數字。從第一行開始，每次可以向左下或者右下走一格，直至走到最後一行。把沿途經過的數字加起來，得到的最大值是多少？

這個三角形看起來形似楊輝三角，也有些像一棵樹，其實這是一個標準的有向無環圖。從第一行到最後一行，可以分成n個步驟，而每個步驟有兩種選擇（第一層除外），那麼一共有2^(n-1)條路徑。如果採用遞歸枚舉演算法，複雜度是指數級別。

高效的演算法是動態規劃，這種演算法常用於圖論問題中求最優解，其核心是狀態和狀態轉移方程。

首先定義狀態，假設 d( i , j )表示從第 i 行 第 j 個數字到低底層的最佳路徑之和，那麼有

d( i , j ) = a( i , j ) + max { d( i + 1, j ) , d( i + 1, j +1 ) } ，這就是狀態轉移方程，方程的特點是全局最優解包含局部最優解。

int dp(int i, int j) { if (i >= a.length) { return 0; } return a[i][j] + Math.max(dp(i + 1, j), dp(i + 1, j + 1));}

這裡存在重複計算的問題，因為動態規劃中存在著重複子問題（想想為什麼樹中不會存在）。怎樣消除重複計算呢？記憶化搜索，或者遞推。

private int[][] a;private int[][] b; // 裡面的元素初始值是-1int dp(int i, int j) { if (i >= a.length) { return 0; } if (b[i][j] >= 0) { return b[i][j]; } return b[i][j] = a[i][j] + Math.max(dp(i + 1, j), dp(i + 1, j + 1));}

記憶化搜索需要輔助空間來記錄中間的計算結果，下面寫一個遞推版本。

int recurrence() { int len = a.length; int[][] d = new int[len][len]; d[len - 1] = a[len - 1].clone(); for (int i = len - 2; i >= 0; i--) { for (int j = 0; j < i + 1; j++) { d[i][j] = a[i][j] + Math.max(d[i + 1][j], d[i + 1][j + 1]); } } // 列印計算結果 for (int[] ints : d) { System.out.println(Arrays.toString(ints)); } return d[0][0];}

遞歸和搜索化的時間複雜度都是O(n^2)。

最後給出測試代碼：

public class NumberTriangle { public NumberTriangle(int[][] a) { this.a = a; b = new int[a.length][a.length]; for (int[] ints : b) { Arrays.fill(ints, -1); } } private int[][] a; private int[][] b; public static void main(String[] args) { Scanner scanner = new Scanner(System.in); int n = scanner.nextInt(); scanner.nextLine(); int[][] a = new int[n][n]; for (int i = 0; i < n; i++) { System.out.print("line " + i + ": "); String input = scanner.nextLine(); List<Integer> list = Stream.of(input.split("\s+")).map(Integer::parseInt).collect(Collectors.toList()); for (int j = 0; j < i + 1; j++) { a[i][j] = list.get(j); } } NumberTriangle triangle = new NumberTriangle(a); System.out.println(triangle.dp(0, 0)); }}

參考：《演算法競賽入門經典》

推薦閱讀：