动态规划入门——记忆化搜索

---

记忆化搜索

1.数塔问题

【动规：递归求解】

递推方程：

• 不难发现，最后一层的点到最后一层的最大距离即为自己对应的值a[n - 1][y]，这个就是问题的边界。
• 从后往前推，观察发现当前点的状态只与正下方和右下方的状态有关，因此得出递推式（状态转移方程）：d[i][j] = a[i][j] + max(a[i+1][j],a[i + 1][j + 1])

既然有了上述的递推式，我们直到递归和递推其实是相互的，因此递推可以改写成递归的形式。

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 500 + 10;
int a[N][N];
int d[N][N];
int n;
int ans = -1e9;

// 求从点（x,y）开始，走到最后一层，经过数字的最大和。
int fun(int x, int y)
{
    if(x == n) return a[x][y];// 最后一层的解就是自己
    return a[x][y] + max(fun(x + 1, y), fun(x + 1, y + 1));// 如果不是最后一行就递归计算
}

int main()
{
    cin >> n;
    for(int i = 1; i <= n; i ++)
        for(int j = 1; j <= i; j ++)
            cin >> a[i][j];

    cout << fun(1, 1);
    return 0;
}
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

缺点：

• 效率太低了，并不是因为递归就效率低，而是因为存在了大量的重复计算。（类比递归式的斐波那契数列）

• 递归存在着大量不必要的重复计算，，递归的层数就越多，算的就越多，重复的计算更多！

【动规：记忆化搜索】

上述方法，存在着大量的重复计算，那我们如何在使用递归的情况下去优化，免去那些不必要的重复计算呢？

如上图，我们在求d[2][1]的时候就把d[3][2]计算过了，而我们再求d[2][2]的时候，又把d[3][2]再计算了一次，这就造成了重复计算？那如何解决呢？

在计算d[2][1]的时候就把d[3][2]计算过了，可以把d[3][2]用一个数组存下来，当再次需要d[3][2]时，就不需要再去递归求解了，直接用数组中备份过的数据就行——这就是记忆化搜索！

动规：记忆化搜索：

• 求解每一个点的值，先判断该点的值是否曾经求解过，如果曾经求解过，直接拿过来使用；如果没求解过，递归求解，并存储该解！
• 将计算过的值存储到一个数组中
• 如何判断是否求解过呢？——做标记判断

【代码实现】

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 500 + 10;
int a[N][N];
int d[N][N];
int n;
int ans = -1e9;

//动规，记忆化搜索：先将d数组初始化为-1，方便判断有没有求解过
int fun(int x, int y)
{
    if(x == n) return a[x][y];// 最后一层的解就是自己
    else
    {
        if(d[x][y] != -1) return d[x][y];// 曾经求解过
        else 
        {
            //求解（x,y)点走到底层经过的数字和的最大值，并存储
            d[x][y] = a[x][y] + max(fun(x + 1, y), fun(x + 1, y + 1));
            return d[x][y];
        }
    }
}

int main()
{
    cin >> n;
    for(int i = 1; i <= n; i ++)
        for(int j = 1; j <= i; j ++)
            cin >> a[i][j];
    
    memset(d, -1, sizeof d);
    cout << fun(1, 1);
    return 0;
}
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
31
32
33
34
35
36
37
38
39

当然数塔问题也可以用递推还有dfs深搜（会爆炸）的方式来求解。

2.滑雪

dfs深搜代码如下：

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 310;
int h[N][N];
int n, m;
int ans = -1e9;

int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};


int dfs(int x, int y, int len)
{

    if(len > ans) ans = len;
    
    for(int i = 0; i < 4; i ++)
    {
        int a = x + dx[i], b = y + dy[i];
        if(a >= 0 && a < n && b >= 0 && b < m && h[x][y] > h[a][b])
        {
            dfs(a, b, len + 1);
        }
    }
}

int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 0; i < n; i ++ )
        for (int j = 0; j < m; j ++ )
            scanf("%d", &h[i][j]);
    
    memset(dp, -1, sizeof dp);
    
    for (int i = 0; i < n; i ++ )
        for (int j = 0; j < m; j ++ )
           {
               int len = 0;
               dfs(i, j, len);
           }
    printf("%d", ans + 1);
    return 0;
}
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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47

dfs爆搜会超时！

本来是一个dfs的过程，遍历所有的位置，找到从当前位置往下走的最大路径，再取最大值，单纯递归深搜的缺点就在于：存在着大量的重复计算。因此我们可以用一个数组，将把遍历过的位置往下走的路径的最大值进行记录，再次遇到直接拿来使用即可，这就是记忆化搜索(空间换时间)。

思路：dfs + 记忆化

​ 遍历每个点作为起点
​ 然后检测该点四周的点 如果可以滑动到其他的点
​ 那么该点的最大滑动长度 就是其他可以滑到的点的滑动长度+1

【代码实现】

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 310;
int h[N][N];
int dp[N][N]; 记录从（x，y）点能滑雪的最长距离 
int n, m;

int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};

//递归 + 记录结果 == 记忆化搜索（DP的一种）
int dfs(int x, int y)
{
    if(dp[x][y] != -1) return dp[x][y];// 被计算过了，直接拿，不用再次计算
    dp[x][y] = 1;// 初始化
    
    for(int i = 0; i < 4; i ++)
    {
        int a = x + dx[i], b = y + dy[i];
        if(a >= 0 && a < n && b >= 0 && b < m && h[x][y] > h[a][b])
        {
            dp[x][y] = max(dp[x][y], dfs(a, b) + 1);
        }
    }
    return dp[x][y];
}

int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 0; i < n; i ++ )
        for (int j = 0; j < m; j ++ )
            scanf("%d", &h[i][j]);
    
    memset(dp, -1, sizeof dp);
    int res = 0;
    for (int i = 0; i < n; i ++ )
        for (int j = 0; j < m; j ++ )
           res = max(res, dfs(i ,j));
    printf("%d", res);
    return 0;
}
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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45

总结

记忆化深搜，其实就是对递归dfs暴力的一种优化，将计算过的记录下来，避免重复计算。记忆化深搜也属于DP的一种！

最常见的DP就是那种寻找状态转移方程（递推式）递推求解的了。