大家好，又见面了，我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。
Jetbrains全系列IDE使用 1年只要46元 售后保障 童叟无欺
前言
前一篇博客写到入门的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];
}
代码解释：
第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;
}
我交上去的时候显示运行时间和用dp写的一样。
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/164450.html原文链接：https://javaforall.net
