DFS 记忆化搜索实战技巧与总结

不同路径

网格类问题的典型代表，状态转移方程通常与坐标相关。

思路分析

函数头设计只需 i 和 j 的坐标。返回条件设定为边界外返回 0，起点返回 1。记忆化搜索需要创建二维备忘录，递归前查表，返回前存表。

代码实现

class Solution {
public:
    int memo[102][102];
    
    int uniquePaths(int m, int n) {
        return dfs(m, n);
    }
    
    int dfs(int m, int n) {
        // 往备忘录中查找一下
        if (memo[m][n]) return memo[m][n];
        
        // 返回条件
        if (m == 0 || n == 0) return 0;
        
        // 第一个点
        if (m == 1 && n == 1) {
            memo[m][n] = 1;
            return 1;
        }
        
        memo[m][n] = dfs(m - 1, n) + dfs(m, n - 1);
        return memo[m][n];
    }
};

// 动态规划版本
class Solution {
public:
    int uniquePaths(int m, int n) {
        vector<vector<int>> dp(m + 1, vector<int>(n + 1));
        dp[1][1] = 1;
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (i == 1 && j == 1) continue;
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
            }
        }
        return dp[m][n];
    }
};

最长递增子序列

这道题展示了如何在一维数组中寻找最优解，状态定义是关键。

思路分析

记忆化搜索方面，每次枚举以 pos 位置为起点的最长递增子序列，让 pos+1 位置的值和 pos 位置比较大小，如果大于就加一。函数体需要 pos+1 到 n-1 位置，dfs 负责找到最大递增子序列，+1 是加上本身。

动态规划则是从后往前添加状态，外层循环枚举位置，内层循环比较大小，更新最长递增子序列到 dp[i] 中。内层循环结束后，更新全局最长的子序列。

代码实现

class Solution {
public:
    int memo[2510];
    
    int lengthOfLIS(vector<int>& nums) {
        int ret = 1;
        // 每次以 i 位置为起点往后搜索
        for (int i = 0; i < nums.size(); i++) {
            ret = max(dfs(nums, i), ret);
        }
        return ret;
    }
    
    int dfs(vector<int>& nums, int pos) {
        if (memo[pos] != 0) return memo[pos];
        int ret = 1;
        for (int i = pos + 1; i < nums.size(); i++) {
            if (nums[i] > nums[pos]) ret = max(ret, dfs(nums, i) + 1);
        }
        memo[pos] = ret;
        return memo[pos];
    }
};

// 动态规划版本
class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        int n = nums.size();
        // 最短的子序列都是 1
        vector<int> dp(n, 1);
        int ret = 1;
        for (int i = n - 1; i >= 0; i--) {
            for (int j = i + 1; j < n; j++) {
                if (nums[j] > nums[i]) {
                    dp[i] = max(dp[i], dp[j] + 1);
                }
            }
            ret = max(ret, dp[i]);
        }
        return ret;
    }
};

猜数字大小 II

博弈论结合 DP 的经典题型，重点在于最小化最大损失。

思路分析

从暴搜入手，转为记忆化搜索。算法原理是在区间 [1, n] 固定一个点 i，分为左右区间，寻找花费最小金钱达到必胜的方案。方案数不止一种，需要在左右枝中寻找所花费金额的最大值才能胜利。函数头传参左右区间，函数体实现寻找多种方案中的最小花费和当前方案下的最大金钱，出现重复数据使用记忆化搜索。

代码实现

class Solution {
public:
    int memo[201][201];
    
    int getMoneyAmount(int n) {
        // 计算出所有方案数中的最小花费
        return dfs(1, n);
    }
    
    int dfs(int left, int right) {
        if (left >= right) return 0;
        if (memo[left][right] != 0) return memo[left][right];
        
        int ret = INT_MAX;
        for (int head = left; head <= right; head++) {
            int x = dfs(left, head - 1);
            int y = dfs(head + 1, right);
            ret = min(ret, max(x, y) + head);
        }
        memo[left][right] = ret;
        return ret;
    }
};

矩阵中的最长递增路径

图论与 DFS 的结合，利用方向数组简化代码。

思路分析

算法原理是从一个点开始 DFS，暴力枚举出每一个递增的路径，返回其中最长的路径即可。DFS 函数设计需要 i、j 坐标去搜索每一个位置。记忆化数组用于缓存结果，如果出现相同路径，不用再次 DFS，直接返回即可。

代码实现

class Solution {
public:
    int memo[201][201];
    int m, n;
    
    int longestIncreasingPath(vector<vector<int>>& matrix) {
        int ret = 1;
        m = matrix.size(), n = matrix[0].size();
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                ret = max(ret, dfs(matrix, i, j));
            }
        }
        return ret;
    }
    
    int dx[4] = {-1, 1, 0, 0};
    int dy[4] = {0, 0, -1, 1};
    
    int dfs(vector<vector<int>>& matrix, int i, int j) {
        if (memo[i][j]) return memo[i][j];
        int ret = 1;
        for (int k = 0; k < 4; k++) {
            int x = dx[k] + i, y = dy[k] + j;
            if (x >= 0 && x < m && y >= 0 && y < n && matrix[x][y] > matrix[i][j]) {
                ret = max(ret, dfs(matrix, x, y) + 1);
            }
        }
        memo[i][j] = ret;
        return ret;
    }
};

总结

1. 记忆化搜索就是先把暴力的 DFS 写出来，然后加一个备忘录优化。
2. 记忆化搜索也和常规的动态规划是一样的，即记忆化搜索也可以改为动态规划的代码。
3. 出现大量重复的数据可以使用记忆化搜索，记忆化搜索可以使原本 O(2^n) 时间复杂度降为 O(n)。