記憶化：如何將程序的運行速度提高10000倍？

來自專欄 如何快速高效學習C++？

坦白地說，本文的標題有標題黨的嫌疑，不過接著往下看你會發現此言不假。

一、什麼是記憶化？

記憶化即一種保存中間計算結果以避免重複計算以加速程序運行的方法，其核心思想是：以空間換時間。

至於能加速多少，極端的情況下，可以達10000倍。

不妨用一個例子來直觀地感受一下：

二、程序示例

#include<iostream>using namespace std;int Fibonacci(int n){//遞歸的計算斐波那契數列的方法，存在大量的重複計算，效率極低 if(n<=0)return 0; if(n==1||n==2)return 1; return Fibonacci(n-1)+Fibonacci(n-2);}long long memo[4300]{};//用於保存中間結果long long Fibonacci2(int n){//遞歸計算的改進版，增加了一個數組memo用於保存中間結果 if(n<=0)return 0; if(memo[n])return memo[n];//如果memo[n]不為零，說明Fibonacci(n)已經被計算過，直接輸出結果即可 if(n==1||n==2)return memo[n]=1; return memo[n]=Fibonacci2(n-1)+Fibonacci2(n-2);}long long Fibonacci3(int n){//樸素的計算Fibonacci演算法，複雜度為O(n) if(n<=0)return 0; int a=0,b=1; while(--n){ a+=b; swap(a,b); } return b;}int main(){ clock_t st=clock();//用於計時 for(int i=1;i<=42;i++){ cout<<endl<<i<<":"<<Fibonacci(i)<< ; } cout<<endl<<"遞歸演算法一共耗時："<<(clock()-st)/1000<<" ms"<<endl; st=clock(); for(int i=1;i<=4200;i++){ cout<<endl<<i<<":"<<Fibonacci2(i)<< ; } cout<<endl<<"記憶化演算法一共耗時："<<(clock()-st)/1000<<" ms"<<endl; st=clock(); for(int i=1;i<=4200;i++){ cout<<endl<<i<<":"<<Fibonacci3(i)<< ; } cout<<endl<<"樸素演算法一共耗時："<<(clock()-st)/1000<<" ms"<<endl;}

輸出結果：

遞歸演算法一共耗時：4281 ms記憶化演算法一共耗時：47 ms樸素演算法一共耗時：146 ms

注意遞歸Fibonacci演算法只計算了前42項，而記憶化演算法以及樸素演算法計算了4200項，是前者的100倍。所以粗略估計記憶化演算法的效率為4281/47*100約為幾乎是10000倍。

三、實戰運用：記憶化+深度優先搜索

Longest Increasing Path in a Matrix - LeetCode?

leetcode.com

Given an integer matrix, find the length of the longest increasing path.

From each cell, you can either move to four directions: left, right, up or down. You may NOT move diagonally or move outside of the boundary (i.e. wrap-around is not allowed).

Example 1:

nums = [ [9,9,4], [6,6,8], [2,1,1]]

Return 4

Example 2:

nums = [ [3,4,5], [3,2,6], [2,2,1]]

Return 4

咋一看，簡單嘛，無非是找出一條最長的上升路徑嘛，深度優先搜索就可以解決。但毫無疑問地，會超時。

這個時候，需要用到記憶化。

深度優先搜索+記憶化 AC代碼以及詳細注釋：

class Solution {public: int longestIncreasingPath(vector<vector<int>>& matrix) { if(matrix.empty())return 0; vector<vector<int>>mark(matrix.size(),vector<int>(matrix[0].size(),0));//用於保存每個點的最長上升序列長度 int maxlen=INT_MIN;//用於保存最大值 for(int i=0;i<(int)matrix.size();i++){ for(int j=0;j<(int)matrix[i].size();j++){ maxlen=max(maxlen,ms(matrix,mark,i,j));//對每個點進行記憶化深度優先搜索 } } return maxlen; } const int arr[4][2]{{1,0},{-1,0},{0,1},{0,-1}};//搜索的四個方向 int ms(const vector<vector<int>>& matrix,vector<vector<int>>&mark,int r,int c){ if(mark[r][c]>0)return mark[r][c];//如果mark[r][c]不為0，表示(r,c)點已經被搜索過，直接輸出結果即可 for(int i=0;i<4;i++){ int newr=r+arr[i][0],newc=c+arr[i][1]; if(newr>=0&&newc>=0&&newr<mark.size()&&newc<mark[0].size()){//如果(r,c)在合法範圍內 if(matrix[r][c]>matrix[newr][newc]){ mark[r][c]=max(mark[r][c],ms(matrix,mark,newr,newc)+1);//向更深一層搜索後，更新mark[r][c] } } } if(mark[r][c]==0)mark[r][c]=1;//如果mark[r][c]依舊為0，表示它周圍沒有比它更大的數，最長上升序列長度為1，即它本身 return mark[r][c]; }};

提交結果：

PS：

廣告時間啦~

理工狗不想被人文素養拖後腿？不妨關注微信公眾號：