记忆化递归（记忆化搜索）

---

前言

​ 前一篇博客写到入门的dp算法，后来又遇到一个奇怪的变种题目，同样也是可以用dp写的（至少标签是有动态规划）。我看了答案还是有些不能完全理解，于是又去b站翻了翻教程基础DP，其中提到记忆化的递归（也称记忆化搜索），相当于结合了dp和递归的优点（这时我又觉得比DP还厉害），然后就准备写写记忆化递归。

---

目录

​ 1.记忆化递归的解释与分析

​ 2.记忆化递归的应用

---

一、记忆化递归的解释与分析

前面说道它结合了dp和递归的优点，分别是记忆化和逻辑清晰易懂。

下面还是结合斐波那契数列的来理解：

F(0)=F(1)=1;

F(n)=F(n-1)+F(n-2) (n≥2,n∈N*);

这里直接给出函数代码，再进行解释：

int F(int n){
    if(n<2)f[n]=1;			//这里f[]是储存数据的数组
	else if(f[n]==0)		//这里是重点
		f[n]=F(n-1)+F(n-2);
	return f[n];
}
1
2
3
4
5
6

代码解释：

第3行中else if的条件很关键：当f[n]没被计算过，就计算一次。也就是说，如果f[n]已经被计算过储存起来了，那就直接用储存的数据，便不用再计算了。

分析优势：

相对于递归，逻辑清晰易懂，就不用说了。

主要是相对于dp的优势。从上一篇知道dp是将基础全部算出来，然后在这个基础上计算出我们要的那个值，减少了相对普通递归的重复计算。

记忆化递归则更加”投机取巧“了，它只计算了需要用的值并储存起来，而其它不会用到的值不去计算，最大化地减少了计算。打个比方，dp就相当于计算了一个方阵上所有的点（无论有没有利用价值），而记忆化递归相当于计算了方阵上有价值的点，因此记忆化递归的运行时间可能比dp还要短。（注意只是可能，因为斐波那契数列无论是dp还是记忆化递归，都是要把前面的值全部算出来的）

---

二、记忆化递归的应用

感觉没啥写的,就拿分配宝藏来写shui一写shui吧。题目在这里。

#include <stdio.h>
int W[201],sum,d[201][20001];
int f(int k,int load);
int max(int a,int b);
int main(void){
	int n;
	scanf("%d",&n);
	for (int i = 1; i <= n; ++i){
		scanf("%d",&W[i]);
		sum+=W[i];
	}
	printf("%d\n",sum-2*f(n,sum/2));
	return 0;
}
int f(int k,int load){
	int ret=d[k][load];
	if(ret==0){					//这里就是判断是否被计算过
		if(k==0||load==0)return ret;
		if(W[k]>load)ret=f(k-1,load);
		else
			ret=d[k][load]=max( f(k-1,load),(f(k-1,load-W[k])+W[k]) );
	}
	return ret;
}
int max(int a,int b){
	int m = a;
	if( a < b) m = b;
	return m;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
'
运行
运行

我交上去的时候显示运行时间和用dp写的一样。