算法之記憶化搜尋

文章目錄

• 1.記憶化搜尋定義
• 2.經典題目
• • 2.1 經典題目1
• 3.相關應用

1.記憶化搜尋定義

• 其實就是暴力搜尋的過程中儲存一些已經計算過的狀态（思想類似于動态規劃，儲存計算過的狀态），在暴力搜尋的過程中利用這些計算過的狀态進而減少很大程度上的計算，進而達到時間複雜度上的優化。

2.經典題目

2.1 經典題目1

【問題描述】自定義函數w(a,b,c)。

如果 a ≤ 0 或b ≤ 0 或 c ≤ 0, 則傳回結果: 1;

如果 a ＞ 20 或 b ＞ 20 或 c ＞ 20, 則傳回結果: w(20, 20, 20)；

如果 a ＜ b 且 b ＜ c, 則傳回結果: w(a, b, c-1) + w(a, b-1, c-1) - w(a, b-1, c)

否則傳回結果: w(a-1, b, c) + w(a-1, b-1, c) + w(a-1, b, c-1) - w(a-1, b-1, c-1)

【輸入格式】 輸入三個值a,b,c

【輸出格式】對應的函數的傳回結果

【輸入樣例1】2 2 2

【輸出樣例1】4

【輸入樣例2】10 4 6

【輸出樣例2】523

• 思路：拿到這個題，首先可以想到的就是遞歸的方法，看上去用遞歸可以輕而易舉的解決，但是遞歸的開銷是不一般的大，并且有大量的重複計算，是以，我們可以采用記憶化搜尋的方法記錄下前面計算過的資料，以便下次調用。
• 參考代碼：

#include<bits/stdc++.h>
using namespace std;
const int N=25;
int dp[N][N][N];
int dfs(int a,int b,int c){
	if(a<=0||b<=0||c<=0) return 1;
	if(a>20||b>20||b>20) return dfs(20,20,20);
	//避免重複計算
	if(dp[a][b][c]) return dp[a][b][c];
	if(a<b&&b<c){
		dp[a][b][c]=dfs(a,b,c-1)+dfs(a,b-1,c-1)-dfs(a,b-1,c);
	}else{
		dp[a][b][c]=dfs(a-1,b,c)+dfs(a-1,b-1,c)
		+dfs(a-1,b,c-1)-dfs(a-1,b-1,c-1);
	}
	return dp[a][b][c];
}
int main()
{
	int a,b,c;
	cin>>a>>b>>c;
	cout<<dfs(a,b,c);
	return 0;
} 
           

3.相關應用

• LeetCode之矩陣中最長遞增子序列
• 藍橋杯之迷宮改編
• 藍橋杯之序列計數