【C++刷题】优选算法——递归第四辑

记忆化搜索篇

什么是记忆化搜索？
- 带备忘录的递归
如何实现记忆化搜索？
- a.添加一个备忘录
- b.每次递归返回的时候，把结果放到备忘录里
- c.每次递归进入的时候，先查看一下备忘录
记忆化搜索 vs 常规动态规划：
- 相同点：
  - 都是暴力解法（暴搜）
  - 优化方式都是把已经计算出的结果存起来
- 不同点：
  - 记忆化搜索是递归形式
  - 常规动态规划是递推(循环)形式

问题：

所有的递归（暴搜、深搜），都能改成记忆化搜索吗？
不是的。 只有在递归的过程中，出现了大量完全相同的问题时，才能用记忆化搜索的方式优化。
以暴搜->记忆化搜索->动态规划的流程思路来解决动态规划问题，一定程度上是可行的。暴搜的阶段也可以为确定状态表示，提供一个参考方向。

斐波那契数

// 1 - 递归
int dfs(int n)
{
    if(n == 0 || n == 1) return n;
    return dfs(n-1) + dfs(n-2);
}
int fib(int n)
{
    return dfs(n);
}

// 2 - 记忆化搜索
unordered_map<int, int> memo; // 创建备忘录
int dfs(int n)
{
    if(n == 0 || n == 1)
    {
        if(!memo.count(n)) memo[n] = n; // 返回之间添加备忘录
        return n;
    }

    if(memo.count(n)) return memo[n]; // 进入之前查看备忘录
    else
    {
        memo[n] = dfs(n-1) + dfs(n-2);
        return memo[n];
    }
    
}
int fib(int n)
{
    return dfs(n);
}

// 3 - 动态规划
int fib(int n)
{
    // 0.预处理
    if(n == 0 || n == 1) return n;
    // 1.dp数组
    vector<int> dp(n + 1, 0);
    // 2.初始化
    dp[1] = 1;
    // 3.状态转移方程
    for(int i = 2; i < dp.size(); ++i)
    {
        dp[i] = dp[i-1] + dp[i-2];
    }
    // 4.返回值
    return dp.back();
}

不同路径

// 1 - 记忆化搜索
vector<vector<int>> memo;
int dfs(int i, int j)
{
    if(i == 0 || j == 0)
    {
        memo[i][j] = 1;
        return 1;
    }
    if(memo[i][j] == 0) memo[i][j] = dfs(i - 1, j) + dfs(i, j - 1);
    return memo[i][j];
}
int uniquePaths(int m, int n)
{
    memo = vector<vector<int>>(m, vector<int>(n, 0));
    return dfs(m-1, n-1);
}

// 2 - 动态规划
int uniquePaths(int m, int n)
{
    // 1.dp数组
    vector<vector<int>> dp(m, vector<int>(n));
    // 2.初始化
    for (int i = 0; i < m; ++i)
    {
        dp[i][0] = 1;
    }
    for (int i = 0; i < n; ++i)
    {
        dp[0][i] = 1;
    }
    // 3.状态转移方程
    for (int row = 1; row < m; ++row)
    {
        for (int col = 1; col < n; ++col)
        {
            dp[row][col] = dp[row - 1][col] + dp[row][col - 1];
        }
    }
    // 4.返回值
    return dp.back().back();
}

最长递增子序列

vector<int> memo;
int dfs(vector<int>& nums, int step)
{
    if(memo[step] != 0) return memo[step];
    int ret = 1;
    for(int i = step + 1; i < nums.size(); ++i)
    {
        if(nums[i] > nums[step])
        {
            ret = max(ret, dfs(nums, i) + 1);
        }
    }
    memo[step] = ret;
    return ret;
}
int lengthOfLIS(vector<int>& nums)
{
    memo = vector<int>(nums.size(), 0);

    int ret = 0;
    for(int i = 0; i < nums.size(); ++i)
    {
        ret = max(ret, dfs(nums, i));
    }
    return ret;
}

猜数字大小 II

vector<vector<int>> memo;
int dfs(int start, int end)
{
    if(start >= end) return 0;
    if(memo[start][end] != -1) return memo[start][end];

    int ret = INT_MAX;
    for(int i = start; i <= end; ++i)
    {
        ret = min(ret, i + max(dfs(start, i - 1), dfs(i + 1, end)));
    }
    
    memo[start][end] = ret;
    return ret;
}
int getMoneyAmount(int n)
{
    memo = vector<vector<int>>(n+1, vector<int>(n+1, -1));
    return dfs(1, n);
}

矩阵中的最长递增路径

unordered_multimap<int, int> direction = {
    {0, 1},
    {0, -1},
    {1, 0},
    {-1, 0}
};
vector<vector<int>> memo;
int dfs(vector<vector<int>>& matrix, int i, int j)
{
    if(memo[i][j] != -1) return memo[i][j];

    int ret = 0;
    for(auto& e : direction)
    {
        int x = i + e.first, y = j + e.second;
        if((x >= 0 && x < matrix.size())
        && (y >= 0 && y < matrix[0].size())
        && (matrix[x][y] > matrix[i][j]))
        {
            ret = max(ret, 1 + dfs(matrix, x, y));
        }
    }
    memo[i][j] = ret;
    return ret;
}
int longestIncreasingPath(vector<vector<int>>& matrix)
{
    int m = matrix.size();
    int n = matrix[0].size();
    memo = vector<vector<int>>(m, vector<int>(n, -1));
    int ret = 0;
    for(int i = 0; i < m; ++i)
    {
        for(int j = 0; j < n; ++j)
        {
            ret = max(ret, 1 + dfs(matrix, i, j));
        }
    }
    return ret;
}

阿阿阿顺Yaya

【C++刷题】优选算法——递归第四辑