顺序： 暴力搜索 -> 记忆化搜索 -> 递推

记忆化搜索=暴力+记录答案
递推公式=dfs向下递归公式
递归数组初始值=递归的边界

用mem存已经有的值

[上台阶1] [c++]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include<bits/stdc++.h>
using namespace std;
long long n;
int mem[10000];

int dfs(int x)
{
    if(mem[x]) return mem[x]; //如果已经有值 用现成的 

    int sum=0;
    if(x==1) sum=1;
    else if(x==2) sum=2;
    else sum=dfs(x-1)+dfs(x-2);
    mem[x]=sum;
    return sum;
}
int main()
{
    cin>>n;
    int res=dfs(n);
    cout<<res<<endl;
    return 0;
}

递归中 递是自顶向下把大问题分解为子问题的过程 而归 是自底向上产生答案的过程
此处我们知道了递归搜索树底的答案
由此 我们可以自底向上递推出答案

[上台阶2] [c++]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include<bits/stdc++.h>
using namespace std;
int f[10000];
int n;

int main()
{
    cin>>n;
    f[1]=1;
    f[2]=2;
    if(n==1 || n==2)
    {
        cout<<f[n]<<endl;
        return 0; 
    }
    for(int i=3;i<=n;i++)
    {
        f[i]=f[i-1]+f[i-2];//也就是dfs的状态转移公式
    }
    cout<<f[n]<<endl;
    return 0;
}

需要注意的是
1.想实现记忆化搜索 dfs参数需要尽可能少 因为记忆的时候若有n个参数 需开n维数组存
如这道题 如果额外一个参数sum记总共偷的钱 是不利于记忆化的
2.不应该把不影响到边界的参数放函数中
3.想剪枝那么得尽可能多放能剪枝的参数 (提前结束程序) 所以剪枝和记忆化搜索需要权衡

[acwing1049大盗阿福] [c++]
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
30
#include<bits/stdc++.h>
using namespace std;
int home[10000];
int mem[10000];
int n,T;

int dfs(int x) //x表示正在考虑哪家店
{
    if(mem[x]) return mem[x];
    int sum=0;
    if(x>n) sum=0; //没店就是0
    else sum=max(dfs(x+1),dfs(x+2)+home[x]) //若不选第x家 则看x+1家 若选 则看往后第二家 值要加上home[x]

    mem[x]=sum; //都是套路
    return sum;
}

int main()
{
    cin>>T;
    while(T--)
    {
        cin>>n;
        for(int i=1;i<=n;i++) cin>>home[i];
        memset(mem,0,sizeof mem); //必须记得重置
        int res=dfs(1);
        cout<<res<<endl;
    }
    return 0;
}

mem[i] 存的是 从第i个店铺开始能获取到的最大价值(i-n)

上述都是递归到搜索树最底部再回溯 都是归的过程产生答案
而递推 我们则需要从最底部推回去 推回去 这一点很重要
总而言之就是递归搜索树的底部是什么状态 就要从什么状态开始
这道题的树的底部是搜索到了最后一家店 所以从n开始枚举
从n开始枚举 但方程不变

如果从1开始枚举 则1是底部 首先导入的元素是n 则为 f[i]=max(f[i-1],f[i-2]+home[i])
由于数组越界问题 f下标同时加2等效 f[i+2]=max(f[i+1],f[i]+home[i]) 此时f[i]存的是从1-i个店铺的劫掠最大值 f[n]为答案

[acwing1049大盗阿福2.0] [c++]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include<bits/stdc++.h>
using namespace std;
int home[10000];
int f[10000];

int n,T;
int main()
{
    cin>>T;
    while(T--)
    {
        cin>>n;
        for(int i=1;i<=n;i++) cin>>home[i];
        memset(mem,0,sizeof f); //必须记得重置
        for(int i=n;i>=1;i--) 
        {
            f[i]=max(f[i+1],f[i+2]+home[i]);
        }
        cout<<f[1]<<endl;
    }
    return 0;
}

求最优子问题 dfs(x)=max(dfs(x+1),dfs(x+2))
求子问题的和 dfs(x)=dfs(x+1)+dfs(x+2)

[P1216数字三角形1,。0] [c++]
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
#include<bits/stdc++.h>
using namespace std;
int r;
int a[1010][1010];
int mem[1010][1010];

int dfs(int x1,int y1)
{
    if(mem[x1][y1]) return mem[x1][y1];
    int sum=0;
    if(x>n || y> n) sum=0;
    else sum=max(a[i+1][j],a[i+1][j+1])+g[i][j];
    mem[x1]=sum;
    return sum; 
}

int main()
{
	cin>>r;
	for(int i=1;i<=r;i++)
	{
		for(int j=1;j<=i;j++) cin>>a[i][j];
	}
    int res=dfs(1,1);
    cout<<res<<endl;
	return 0;
}

写递推方程 递推方程便和dfs方程一样 但是需要从搜索树底部开始
即i从n开始枚举
如果要从1开始枚举 这道题中 最下面一行都有可能是终点 需要循环遍历得最大值

[P1216数字三角形2.0] [c++]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include<bits/stdc++.h>
using namespace std;
int r;
int a[1010][1010];
int f[1010][1010];
int main()
{
	cin>>r;
	for(int i=1;i<=r;i++)
	{
		for(int j=1;j<=i;j++) cin>>a[i][j];
	}
	for(int i=r;i>=1;i--)
	{
		for(int j=1;j<=r;j++)
		{
			f[i][j]=max(f[i+1][j],f[i+1][j+1])+a[i][j];
		}
		
	}
	cout<<f[1][1]<<endl; 
	return 0;
}