資料結構與演演算法 | 記憶化搜尋（Memorize Search）
在本系列的文章中已經寫了二元樹(Binary Tree)、深搜（DFS）與廣搜（BFS）、雜湊表（Hash Table）等等，計劃接下來要寫的是動態規劃（Dynamic Programming，DP），它算得上是最靈活的一種演演算法。回憶筆者學習動態規劃的時候，最開始接觸的是經典的 「01揹包」 問題；不過現在想起來，以「01揹包問題」作為初次接觸的動態規劃演演算法的問題_並不友好_；花費了不少時間才慢慢感悟到動態規劃演演算法的核心思想。
先前的文章中涉及了不少搜尋演演算法，在搜尋演演算法上融入動態規劃演演算法思想的 記憶化搜尋（Memorize Search）不妨是一個不錯的_承前啟後_的選擇。相對於 「01揹包」類問題，記憶化搜尋 對初學者 理解 動態規劃 更友好，也能更好的感受到其魅力所在。
記憶化搜尋，所謂 「記憶」 參照 Geeksforgeeks 網站上介紹記憶搜尋原文中一句話就是 「to transform the results of a function into something to remember.」 把函數的結果儲存下來作為 「記憶」。將「記憶」應用於搜尋演演算法上，也就是搜尋到有記錄了函數結果的地方，其實就不需要再進行函數計算，直接返回 「記憶」 的結果即可。
記憶化搜尋是一種自頂向下（Top-Down）分析的演演算法，文字描述過於懸浮於理論，保持本系列文風且用演演算法題來看下記憶化搜尋演演算法具體的內容。
自頂向下（Top-Down）
LeetCode 329. 矩陣中的最長遞增路徑【困難】
給定一個 m x n 整數矩陣 matrix ，找出其中 最長遞增路徑 的長度。
對於每個單元格，你可以往上，下，左，右四個方向移動。 你 不能 在 對角線 方向上移動或移動到 邊界外。（即不允許環繞）。
- 直接順著題意進行分析，找到 「最長遞增路徑」 直接用搜尋遍歷，把 matrix每個單元格的最長遞增路徑都計算下，返回其中最長的路徑。不妨就假設下有一個 search的函數能夠計算出 以當前單元格為起點的最長遞增路徑長度。遍歷過程中 的最大長度 儲存再 max 中，最後返回即可，程式碼如下：
// 假設中的函數
public int search(int[][] matrix,int x,int y){
int max;
return max;
}
public int longestIncreasingPath(int[][] matrix) {
int max = 0;
for (int i = 0; i < matrix.length; i++) {
for (int j = 0; j < matrix[0].length; j++) {
//（i，j）格的最長遞增路徑長度
max = Math.max(max,search(matrix,i,j));
}
}
return max;
}
- 問題開始關鍵點現在變成了 search 函數的實現；接著順著題意分析，可以往上，下，左，右四個方向移動.首先考慮一個方向情況，只往上方向移動且可以往上移動（上方相鄰的單元格大於當前單元格，遞增），那麼此時 當前單元格的最大路徑長度就是
上方單元格的最大路徑 + 1，其中1代表當前單元格。
public int search(int[][] matrix,int x,int y){
int number = matrix[x][y],up = 1;
// 保障可以往「上」移動， x-1 沒有越邊界（ x > 0 ）
// 且是 遞增的 matrix[x-1][y] > number
if( x > 0 && matrix[x-1][y] > number ){
// 遞迴呼叫，同類子問題，（x-1，y）格的最長遞增路徑長度
up += search( matrix, x-1, y );
}
return up;
}
- 如此，擴充套件到 四個方向，最終當前單元格最大路徑就是 四個方向中取最大的返回。
public int search(int[][] matrix,int x,int y){
int number = matrix[x][y],up = 1,down =1,left=1,right=1;
if(x>0 && matrix[x-1][y] > number){
up += search(matrix,x-1,y);
}
if(x+1<matrix.length && matrix[x+1][y] > number){
down += search(matrix,x+1,y);
}
if(y+1<matrix[0].length && matrix[x][y+1] > number){
right += search(matrix,x,y+1);
}
if(y>0 && matrix[x][y-1] > number){
left += search(matrix,x,y-1);
}
return Math.max(Math.max(up,down),Math.max(right,left));
}
-
實現到這裡按照搜尋思路的演演算法已經完成；不過會發現效能不高，分析過程會發現呼叫 search函數 時候，同樣一格位置會計算多次。此時聯絡想想先前提到的 「記憶」 ，把函數的結果儲存下來作為 「記憶」，也就是用 一個二維陣列 cahce 快取起來 已經計算過單元的結果。
search 實現改為 (cache需要在 longestIncreasingPath 根據 matrx大小 new下，這裡略) ，程式碼如下：
public int[][] cache = null;
public int search(int[][] matrix,int x,int y){
if(0 != cache[x][y])
return cache[x][y];
int number = matrix[x][y],up = 1,down =1,left=1,right=1;
if(x>0 && matrix[x-1][y] > number){
up += search(matrix,x-1,y);
}
if(x+1<matrix.length && matrix[x+1][y] > number){
down += search(matrix,x+1,y);
}
if(y+1<matrix[0].length && matrix[x][y+1] > number){
right += search(matrix,x,y+1);
}
if(y>0 && matrix[x][y-1] > number){
left += search(matrix,x,y-1);
}
// 儲存 「記憶」
cache[x][y] = Math.max(Math.max(up,down),Math.max(right,left));
return cache[x][y];
}
- 到此，已經按照記憶化搜尋演演算法思路完成了問題的解決。
回顧下記憶化搜尋解題過程，我們是從演演算法問題出發 -> 分析需要完成的計算（子問題）-> 進一步進行解決。這其實就是 自頂向下（Top-Down）的思考方式。
記憶化搜尋 與 動態規劃
再來看"記憶"，cache[x][y] 所記錄的是 x,y 這個單元格已經計算過的 最大路徑長度。當前單元格 的最大路徑長度使用上、下、左、右四個方向上的單元格 最大路徑長度 來進行計算 ,使用"記憶" 其實就是在使用子問題的最優解。
current_max = Max( up+1, down+1, left+1, right+1 )
另外一個角度描述，規劃決策 當前單元格的最大路徑 是根據 （上、下、左、右）相鄰四個方向上的單元格最大路徑 進行的計算。相鄰四個方向上的最大路徑（子問題最優解） 並非一開始靜態寫入下來，而是在程式執行過程中至少計算一次儲存下來，可看作 動態的計算。根據動態計運算元問題最優結果來進行規劃決策當前最優結果，也就是所謂 動態規劃（Dynamic Programming）的字面意思。
可以多體會下： 解決最佳化問題，根據子問題的最優結果 規劃決策 -> 當前問題最優結果 -> 進而求解最初問題。
所以有一種說法就是：記憶化搜尋 是 動態規劃 自頂向下（Top-Down）分析的一種實現形式，通常用遞回來實現。
最後總結本文
- 本系列文章中寫此篇 承前啟後的思考，記憶化搜尋 的基本概念；
- 通過一道題演示 自頂向下（Top-Down）的分析，實際應用記憶化搜尋解決 具體演演算法問題；
- 解讀 記憶化搜尋 與 動態規劃 的關係，以及動態規劃一些概念；
下一篇咱們再一起繼續解讀 動態規劃（Dynamic Programming） ，歡迎關注 Java研究者專欄、部落格、公眾號等
