问题一：
首先看一个最经典的问题：上台阶问题。P1255 数楼梯 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
我们首先看一下，如何用DFS的方法进行解题。
假设我们要上到第5级台阶：
可以看出上到第五级台阶时，可能是由第4级上去的，也可能是从第3级上去的。接下来以此类推。
所有我们很容易想到一个方程：假设F(x)表示上到第X级台阶的方案数。那么不难看出：
F(x) = F(x-1) + F(x-2)
一开始不要多想直接按照常规的DFS进行，
#include<iostream>
using namespace std;
int n;
int dfs(int x)
{
if(x==1) return 1;
else if(x==2) return 2;
return dfs(x-1) + dfs(x-2);
}
int main()
{
cin>>n;
cout<<dfs(n)<<endl;
return 0;
}但是这个过不了；
再看上面的图，发现很多都算了2遍，比如3。
那么来记忆化搜索：
问题二：
1049. 大盗阿福 - AcWing题库
阿福是一名经验丰富的大盗。趁着月黑风高，阿福打算今晚洗劫一条街上的店铺。
这条街上一共有 𝑁 家店铺，每家店中都有一些现金。
阿福事先调查得知，只有当他同时洗劫了两家相邻的店铺时，街上的报警系统才会启动，然后警察就会蜂拥而至。
作为一向谨慎作案的大盗，阿福不愿意冒着被警察追捕的风险行窃。
他想知道，在不惊动警察的情况下，他今晚最多可以得到多少现金？
输入格式
输入的第一行是一个整数 T𝑇，表示一共有 𝑇 组数据。
接下来的每组数据，第一行是一个整数 𝑁 ，表示一共有 𝑁 家店铺。
第二行是 𝑁 个被空格分开的正整数，表示每一家店铺中的现金数量。
每家店铺中的现金数量均不超过1000。
输出格式
对于每组数据，输出一行。
该行包含一个整数，表示阿福在不惊动警察的情况下可以得到的现金数量。
输入样例：
2
3
1 8 2
4
10 7 6 14
输出样例：
8
24解答题目啦:
首先用DFS的思想想一下：
解释一下：
方块里面的标i记是第i家店。每个店铺都可以进行偷或不偷。但是！当偷了前一个店铺，那么这个店铺就不能再偷了。
还有一点很重要的要注意！我们这里是从第一家（1）先“分”到第4家或第3家，然后还要返回去。也就是说要确定递归的终点，这里可以想到如果到了倒数第一个（4）或倒数第2各（3）都要return 。
那么我们是不是也可以反过来递归呢？
答案当然可以啦。
先看从1开始递归的：
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 100005;
int n;
int arr[N];
int dfs(int x)
{
if(x>n) return 0;//注意这里为什么是只要x>n就可以了？
return max(dfs(x+1),dfs(x+2) + arr[x]);
}
int main()
{
int T;
cin>>T;
while(T--)
{
cin>>n;
for(int i=1;i<=n;i++) cin>>arr[i];
cout<<dfs(1)<<endl;
}
return 0;
}
上面有个小细节：为什么当x>n就可以了呢？不是当此时选了3也就停止了吗？以及为什么这样就可以用dfs直接加上一个数了？
我们这样一步一步分析：
发现：4及以上的都必须是0，而选了3时下一个一定是5，所以直接递归0就OK。也不会执行下面的。
现在我们来记忆化搜索：
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N = 100005;
int n;
int arr[N];
int mum[N];
int dfs(int x)
{
if(mum[x]) return mum[x];
int summ = 0; //创建一个变量用来存储当前节点的数值。
if(x>n) summ = 0; //如果越界那么值为0；
else summ = max(dfs(x+1),dfs(x+2) + arr[x]);//否则将DFS的值赋值给sum
mum[x]=summ; //将summ的值赋值给记忆化数组
return summ; //返回当前层的值。注意如何越界了就不会走else后面的了。这里要和不加else区分开
}
int main()
{
int T;
cin>>T;
while(T--)
{
cin>>n;
for(int i=1;i<=n;i++) cin>>arr[i];
cout<<dfs(1)<<endl;
memset(mum,0,sizeof(mum));
}
return 0;
}有的小伙伴可能会这样想，我要记录最大值，那么我可不可以在DFS函数上面加一个参数呢？这个参数用来记录当前的最大值。
这个思想是可以的，但是我们想一下：加上这个参数能给我们省下什么？加上一个参数，那就说明此时的状态(就是此时的层数和价格组成的笛卡尔积)是一个节点，我们进行记忆化存储的前提是什么？是要存什么？在上面的图中可以看出是要存节点的值（哪一层），现在多加了一个参数，那是不是要用二维数组来存储啊？
而且我们前面在DFS函数中加参数是为了是什么？
是因为这个参数可以影响我们的递归的进行，比如(x1,y1)这个坐标。当然要两个值，因为x和y都不能超出界限，一旦超出那就要return 。和我们这一题比较一下，我们加上当前我们偷的最大值有有什么影响吗？这个最大值没有限制我们递归的进行，所以是不需要加上的，加了反而多此一举。
我们要记住：
当想要剪枝时，在DFS函数中尽可能多的加入可以判断剪枝的参数。
当要记忆化存储时，在DFS函数中尽可能少的加入参数。
接下来，进阶，DP！
对于这个图：
我们的DFS是从4 --> 1 ，然后从1-->4，那我们能不能直接从1到4呢？
答案是可以的：
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N = 100005;
int n;
int arr[N];
int mum[N];
int dp[N];
//int dfs(int x)
//{
// if(mum[x]) return mum[x];
// int summ = 0;
// if(x>n) summ = 0;
// else summ = max(dfs(x+1),dfs(x+2) + arr[x]);
// mum[x]=summ;
// return summ;
//}
int main()
{
int T;
cin>>T;
while(T--)
{
cin>>n;
for(int i=1;i<=n;i++) cin>>arr[i];
// cout<<dfs(1)<<endl;
// memset(mum,0,sizeof(mum));
for(int i=1;i<=n;i++)
{
//dp[i] = max(dp[i-1],dp[i-2] + arr[i-2])
//这里i同时加2
dp[i+2] = max(dp[i+1],dp[i] + arr[i]);
}
cout<<dp[n+2]<<endl;;
}
return 0;
}可能很多人直接接触DP时，很不理解这个给状态转移方程到底咋来的，我们观察上面，它不就是DFS直接从最底层向上推得来的吗？
