引言
这是一个悬壶济世的故事。据说神农尝百草后，将自己的收获撰写成一本书，分发给各个部落的长老。有一天，一个部落里面忽然爆发了各种疾病，为了遏制疾病，部落长老出去寻找能治病的草药。历经千辛万苦，他终于找到了一片福地，这里面的草药应有尽有，然而，有些药近在眼前，能很容易地找到；有些药则远在天边，需要花费很多天才能找到。假设长老知道所有草药的位置，并且能确定采到药的时间，每种药只能救活特定人数的人，且他只有有限的时间用来寻找草药，那么，他该如何采药，才能救活更多的人呢？
正文
首先，我们可以确定的是，爆搜肯定能帮助长老找到最优解，但长老很赶时间，等到爆搜完，村里的人可能都死光光了~所以要找到时间更短的方法。我们思考这样一个问题：总共只有这么几种药，几块地方，爆搜搜来搜去肯定会有一模一样的情况出现。如果我们记住第一次搜索这种情况的答案，等到第二次搜索的时候直接用，是不是就能有效减少搜索的时间了呢？我们按照这个思路写一下：
爆搜思路
如果爆搜的话，我们就直接考虑这个题涉及到多少变量就可以了。显然，题目中包含三种变量：
- 搜索每种草药的时间
- 每种草药能救活多少人
- 长老采药的时间限制
我们直接爆搜这三种变量就可以：
代码
#include<algorithm>
#include<iostream>
using namespace std;
int* time1;//采每种药花费的时间
int* price;//每种药的价值
int sum_time=100;//长老剩余的采药时间
int now_val=0;//现有草药的价值
int n;//草药种数
int ans;//现在的解
int dfs(int i,int sum_time,int now_val)
{
if (sum_time < 0)return;
if (i == n + 1) {//每次搜索完如果符合条件则更新解
ans = max(ans, now_val);
return;
}
//依次枚举采该种药和不采该种药的情况
dfs(i + 1, sum_time, now_val);
dfs(i + 1, sum_time - time1[i], now_val + price[i]);
}
记忆化搜索思路
爆搜算法的时间复杂度是指数级的，肯定行不通。于是我们按照上文思路，记住上一次搜索的答案，在下一次直接用就可以。另外当前采药的价值是由前两种变量决定的，因此可以只搜索两个变量，每次将第三个变量的答案通过数组存起来就可以了。
这种减少维度的思想在合并石头的最低成本中也用到过。
代码
#include<algorithm>
#include<iostream>
using namespace std;
int* time1;//采每种药花费的时间
int* price;//每种药的价值
int sum_time=100;//长老剩余的采药时间
int** now_val;//用二维数组来存储第i种草药采或不采的价值
int n;//草药种数
int ans;//现在的解
int dfs(int i,int sum_time)//搜索第i种草药，省去了第三个变量，改用数组存储。
{
if (sum_time < 0)return;
if (now_val[i][sum_time] != -1) {
return now_val[i][sum_time];
}
if (i == n + 1)now_val[i][sum_time] = 0;
int dfs1, dfs2;
dfs1 = dfs(i + 1, sum_time);
dfs2 = dfs(i + 1, sum_time - time1[i])+price[i];
return now_val[i][sum_time] = max(dfs1, dfs2);
}
递推思路
分析一下，这道题满足动态规划的三个特征：
- 最优子结构：大问题的最优解是所有小问题最优解的最大值
- 无后效性：不能回头去采已经采过的药
- 重叠子问题：我们分析记忆化搜索的时候就知道肯定会有完全一样的子问题。
因此可以用动态规划的方法解决。
代码
#include<algorithm>
#include<iostream>
using namespace std;
int* time1;//采每种药花费的时间
int* price;//每种药的价值
int sum_time=100;//长老剩余的采药时间
int** now_val;//用二维数组来存储第i种草药采或不采的价值
int n;//草药种数
int ans;//现在的解
int dp()
{
for (int i = 0; i < n; i++) {
for (int j = sum_time; j >=0; j++) {//起始状态是从第0种草药开始选择，剩余时间为初始的sum_time
if (j >= time1[i]) {
now_val[i][j] = max(now_val[i - 1][j], now_val[i - 1][j - time1[i]] + price[i]);//不采或采
}
else {
now_val[i][j] = now_val[i - 1][j];//只能选择不采
}
}
}
}
总结
简要比较一下记忆化搜索和递推代码，你会发现他们的答案都是通过比较两个东西的最大值来得出的，而且这两个东西都是之前求好的，所以他们的思维方式及其相似，都使用了空间换时间的思想，时间复杂度也是差不多的。
与动态规划相比，记忆化搜索比较好写，无需考虑状态转移方程，而且处理边界比较方便（上文的记忆化只用了一个if条件来处理）。但是由于存在递归，因此效率会低于动态规划，而且难以优化，需要取舍。
如何写出记忆化搜索
上文是从爆搜代码优化到记忆化搜索的，我们可以总结为：
- 写出爆搜代码
- 减小维度，去除不必要变量
- 写出存储数组
当然也可以从动态规划到记忆化搜索：
- 写出dp代码
- 用状态转移方程写出对应的dfs函数
- 写出存储数组
————————分割线——————————
我是霜_哀，在算法之路上努力前行的一位萌新，感谢你的阅读！码文不易，如果觉得好的话，可以关注一下，我会在将来带来更多更全面的算法讲解！