算法：记忆化搜索

概述

记忆化搜索是一种典型的空间换时间的思想。
记忆化搜索的典型应用场景是可能经过不同路径转移到相同状态的dfs问题。
更明确地说，当我们需要在有层次结构的图（不是树，即当前层的不同节点可能转移到下一层的相同节点）中自上而下地进行dfs搜索时，大概率我们都可以通过记忆化搜索的技巧降低时间复杂度。

例子：青蛙过河

题目描述

一只青蛙想要过河。 假定河流被等分为若干个单元格，并且在每一个单元格内都有可能放有一块石子（也有可能没有）。 青蛙可以跳上石子，但是不可以跳入水中。

给你石子的位置列表 stones（用单元格序号 升序 表示）， 请判定青蛙能否成功过河（即能否在最后一步跳至最后一块石子上）。

开始时， 青蛙默认已站在第一块石子上，并可以假定它第一步只能跳跃一个单位（即只能从单元格 1 跳至单元格 2 ）。

如果青蛙上一步跳跃了 k 个单位，那么它接下来的跳跃距离只能选择为 k - 1、k 或 k + 1 个单位。 另请注意，青蛙只能向前方（终点的方向）跳跃。

示例1

输入：stones = [0,1,3,5,6,8,12,17]
输出：true
解释：青蛙可以成功过河，按照如下方案跳跃：跳 1 个单位到第 2 块石子, 然后跳 2 个单位到第 3 块石子, 接着 跳 2 个单位到第 4 块石子, 然后跳 3 个单位到第 6 块石子, 跳 4 个单位到第 7 块石子, 最后，跳 5 个单位到第 8 个石子（即最后一块石子）。
1
2
3

示例2

输入：stones = [0,1,2,3,4,8,9,11]
输出：false
解释：这是因为第 5 和第 6 个石子之间的间距太大，没有可选的方案供青蛙跳跃过去。
1
2
3

分析

对于我构造的示例 stones = [0,1,3,4,5,6,7,10,15]，搜索路径如下：

可以看到从状态[5,1]和状态[5,2]都能转移到状态[7,2]，而[7,2]这个状态并不能转移到终点这个结论是可以被存储起来的，避免对同一个结论的重复计算。

就好比很多人走迷宫，前人走到[7,2]发现没有路能走出去（无法转移到目标状态），他回到这个节点（回溯）时在此立下告示牌（记忆化标签），告诉后人不要来这个地方，来了也是白来，后人看到告示牌自然就去尝试其他可能能走出去的路即可（转移到没有打上记忆化标签的状态）。前人栽树后人乘凉。

代码

/*
细节：dfs中的参数pos不是位置，而是位置在数组中的下标。这样便于在vector中记录。
*/

class Solution {
public:
    vector<unordered_map<int, bool>> flag;

    
    bool dfs(int pos, int preJump, vector<int>& stones) {
        if(pos == stones.size()-1) return true;
        if (flag[pos].count(preJump)) {
            return false;
        }

        for(int jump = preJump-1; jump<=preJump+1; jump++) {
            if(jump<=0) continue;
            int nextpos = lower_bound(stones.begin(), stones.end(), stones[pos]+jump) - stones.begin();
            if(nextpos != stones.size() && stones[nextpos] == stones[pos]+jump && dfs(nextpos, jump, stones)) {
                return true;
            }
        }

        return flag[pos][preJump] = false;
    }

    bool canCross(vector<int>& stones) {
        int n = stones.size();
        flag.resize(n);
        return dfs(0, 0, stones);
    }
};
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

在学习算法的初期，最需要锻炼的就是对症下药的能力。下面来看一道典型不能使用记忆化搜索的反例：

反例：停在原地的方案数

题目描述

有一个长度为 arrLen 的数组，开始有一个指针在索引 0 处。

每一步操作中，你可以将指针向左或向右移动 1 步，或者停在原地（指针不能被移动到数组范围外）。

给你两个整数 steps 和 arrLen ，请你计算并返回：在恰好执行 steps 次操作以后，指针仍然指向索引 0 处的方案数。

由于答案可能会很大，请返回方案数 模 10^9 + 7 后的结果。

示例1

输入：steps = 3, arrLen = 2
输出：4
解释：3 步后，总共有 4 种不同的方法可以停在索引 0 处。
向右，向左，不动
不动，向右，向左
向右，不动，向左
不动，不动，不动
1
2
3
4
5
6
7

示例2

输入：steps = 2, arrLen = 4
输出：2
解释：2 步后，总共有 2 种不同的方法可以停在索引 0 处。
向右，向左
不动，不动
1
2
3
4
5

分析

如图所示，图中每个节点S值表示当前还剩多少步要走，pos值表示当前处在的位置。每个节点对应一个方案数，我们要计算的是根节点(S=3,pos=0)的方案数。

乍一看本题也是自上而下在有层次结构的图中搜索，且也符合当前层的不同节点都转移到下一层的同一节点。但问题在于本题并不是dfs过程，因为要想知道(S=2,pos=1)节点的值，需要同时知道(S=1,pos=0)、(S=1,pos=1)、(S=1,pos=2)这三个节点的值。其实对于计算方案数的问题，最先想到的方法应该是动态规划。事实证明这道题的确用动态规划是最好的解法。

动态规划之所以能比递归快很多，就是通过将重复子问题的解存储起来，重复子问题的解只需算一次即可，不必重复计算，自底向上一步步得到原问题的解。从这个角度来说，动态规划和记忆化搜索的共同点在于都是空间换时间的思想。

回到本题的dp解法：

dp定义：dp[i][j] 表示还可以走i步时，位于位置j的方案数
初始化：dp[0][0] = 1
待求结果：dp[steps][0]
状态转移方程：dp[i][j] = dp[i-1][j] + dp[i-1][j-1] + dp[i-1][j+1]
1
2
3
4

代码

class Solution {
public:
    int numWays(int steps, int arrLen) {
        // dp[i][j] 表示还剩i个step时位于位置j的方案数。要求dp[steps][0]
        // 由于steps步后，位置最远走到steps,因此列数应该是min(steps+1,arrLen)
        int col = min(steps+1, arrLen);
        vector<vector<int>> dp(steps+1,vector<int>(col, 0));  
        // init
        dp[0][0] = 1;
        int mod = 1000000000+7;
        for(int i=1;i<=steps;i++) {
            for(int j=0;j<col;j++) {
                dp[i][j] = (dp[i][j] + dp[i-1][j]) % mod;
                if(j-1>=0) dp[i][j] = (dp[i][j] + dp[i-1][j-1]) % mod;
                if(j+1<col) dp[i][j] = (dp[i][j] + dp[i-1][j+1]) % mod;
                if(i==steps && j==0) break;
            }
        }
        return dp[steps][0];
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

滚动数组优化：

class Solution {
public:
    int numWays(int steps, int arrLen) {
        // 由于steps步后位置最远走到steps,因此列数可以优化为min(steps+1,arrLen)。可以大大降低空间和时间复杂度
        // 由于转移到dp[i]只需要dp[i-1]，因此使用滚动数组，可以将dp数组的行数优化为2。
        int col = min(steps+1, arrLen);
        vector<vector<int>> dp(2,vector<int>(col, 0));  
        // init
        dp[0][0] = 1;
        int mod = 1000000000+7;
        for(int i=1;i<=steps;i++) {
            for(int j=0;j<col;j++) {
                int dst = i%2, src = 1 - i%2 ;  // i为奇数时从[0]转移到[1]，反之亦然
                dp[dst][j] = 0;  // 不要忘记将待填充的dp初值设为0，因为里面保存这之前的数据
                dp[dst][j] = (dp[dst][j] + dp[src][j]) % mod;
                if(j-1>=0) dp[dst][j] = (dp[dst][j] + dp[src][j-1]) % mod;
                if(j+1<col) dp[dst][j] = (dp[dst][j] + dp[src][j+1]) % mod;
                if(i==steps && j==0) break;
            }
        }
        
        if(steps % 2) return dp[1][0];
        return dp[0][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