算法之记忆化搜索_艾宾浩斯记忆曲线的算法实现

大家好，又见面了，我是你们的朋友全栈君。

文章目录

• 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之矩阵中最长递增子序列
• 蓝桥杯之迷宫改编
• 蓝桥杯之序列计数

发布者：全栈程序员栈长，转载请注明出处：https://javaforall.cn/189136.html原文链接：https://javaforall.cn