遞歸原來可以so easy|-連載（4）

對遞歸進行優化--記憶化

遞歸可以很方便的解決很多問題，讓程序變得很簡潔。

但是，在遞歸解決問題的過程成，有時候會有很多重複計算,使得計算量很大，耗時很長。

比如，使用遞歸求斐波那契數列。

如果用普通的遞歸來解，當n值很大時，時間會很長而超時。

如圖，當n等於45時，需要運行5秒才能求出結果。

分析一下，會是什麼原因導致需要計算這麼長時間呢？

根據斐波那契數列的遞推公式：

fn=f(n-1)+f(n-2)

f(n-1)=f(n-2)+f(n-3)f(n-2)=f(n-3)+f(n-4);以上3行合併一下：fn=( f(n-2)+f(n-3) ) + ( f(n-3)+f(n-4) )

可以看到， f(n-3)被重複計算了。

再看一下斐波那契數列的運行時圖：

可以看到，有大量的重複計算。

有沒有什麼辦法可以優化呢？

如果我們能記錄一些狀態的中間結果，在需要的時候直接讀取結果，就可以減少重複計算。

這個思想叫著記憶化。

對於斐波那契數列，我們可以把計算完 n=2,n=3時...的值保存在數組中，下次需要使用他們來計算其他n值時，從數組中取出來，而不去再計算。

按照這個思想，代碼修改為：

可以看到，經過記憶化優化後的程序，運行速度快了很多。

下面我們再看個例子。

數字三角形問題

573 88 1 02 7 4 44 5 2 6 5如上圖所示，第一行有一個數字5，表示數字三角形共有5層。

後面5行為各層的數字,組成一個數字三角形。

給出一個三角形，從三角形的頂點，只能走左下方或者右下方，然後把所遍歷的數字加起來，求出最大的值。比如對於上圖來說，答案就是30(7+3+8+7+5)。

現給定一個任意的數字三角形，輸出最大的值。

我們從頂點(也就是第一行第一列)開始走，其最大值為頂點的值加上從他下面兩個數開始，走到底邊的最大值中，更大的那個，由此，我們把問題分解成求第一行的數字到底邊的最大值，到求第二行的數字到底邊的最大值，這就形成了遞歸。而遞歸的終止條件是到了最後一行，其值就是它本身。遞歸的代碼如下：

package test; ? import java.util.Scanner; ? public class Hello { static int d[][] = new int[100][100]; // 最多100層 static int n; ? public static void main(String[] args) { Scanner sc = new Scanner(System.in); n = sc.nextInt(); // 總共有幾層 for (int i = 1; i <= n; i++) for (int j = 1; j <= i; j++) d[i][j] = sc.nextInt(); int m = MaxSum(1, 1); System.out.println("最大值："+m); } ? static int MaxSum(int l, int r) { if (l == n) return d[l][r]; else return Math.max(MaxSum(l + 1, r), MaxSum(l + 1, r + 1)) + d[l][r]; } ? }

樣例輸入輸出：

輸入：

6 2 96 30 83 52 60 21 65 44 61 8 79 50 41 21 61 41 50 38 79 10

輸出375

如果通過記憶化進行優化呢？

思考一下........

....................................................................................................................

? public class Hello { static int d[][] = new int[100][100]; // 最多100層 static int max[][]= new int[100][100]; //保存記憶 static int n; ? public static void main(String[] args) { Scanner sc = new Scanner(System.in); n = sc.nextInt(); // 總共有幾層 for (int i = 1; i <= n; i++) for (int j = 1; j <= i; j++) d[i][j] = sc.nextInt(); int m = MaxSum(1, 1); System.out.println("最大值："+m); } ? static int MaxSum(int l, int r) { if (l == n) return d[l][r]; else { if(max[l][r]!=0) { return max[l][r]; }else { int x=Math.max(MaxSum(l + 1, r), MaxSum(l + 1, r + 1)) + d[l][r]; max[l][r]=x; return x; } } } }