【递归，搜索与回溯算法】记忆化搜索（二）

📝前言说明：

• 本专栏主要记录本人递归，搜索与回溯算法的学习以及LeetCode刷题记录，按专题划分
• 每题主要记录：（1）本人解法 + 本人屎山代码；（2）优质解法 + 优质代码；（3）精益求精，更好的解法和独特的思想（如果有的话）
• 文章中的理解仅为个人理解。如有错误，感谢纠错

🎬个人简介：努力学习ing
📋本专栏：C++刷题专栏
📋其他专栏：C语言入门基础，python入门基础，C++学习笔记，Linux
🎀CSDN主页 愚润泽

你可以点击下方链接，进行该专题内不同子专题的学习

题单汇总链接：点击 → 题单汇总

300. 最长递增子序列

题目链接：https://leetcode.cn/problems/longest-increasing-subsequence/description/

优质解

思路：

• 暴搜：以i位置为开始的最长递增子序列的长度
  • 递归函数头：给一个pos返回以pos为开始的最长递增子序列的长度
  • 最后对所有开始位置遍历一遍找到最大的
• 加记忆化搜搜

代码：

class Solution {
public:
    int dfs(vector<int>& nums, vector<int>& memo, int pos)
    {
        if(memo[pos]) return memo[pos];
        int ret = 1; // 记录返回值（当子序列元素为 1 时，默认为 1）
        for(int i = pos + 1; i < nums.size(); i++) // 下一个元素
        {
            if(nums[i] > nums[pos])
                ret = max(ret, dfs(nums, memo, i) + 1);
        }
        memo[pos] = ret; // 加入备忘录
        return ret;
    }
      
    int lengthOfLIS(vector<int>& nums) {
        int n = nums.size();
        vector<int> memo(n);
        int ans = 1;
        for(int i = 0; i < n; i++)
        {
            ans = max(ans, dfs(nums, memo, i));
        }
        return ans;
    }
};

时间复杂度：$O(n^2)$
空间复杂度：$O(n)$

375. 猜数字大小 II

题目链接：https://leetcode.cn/problems/guess-number-higher-or-lower-ii/description/

优质解

思路：

• 按区间来填充备忘录

代码：

class Solution {
public:
    int dfs(int left, int right, vector<vector<int>>& memo)
    {
        if(left >= right) // 必选中答案
            return 0;
        if(memo[left][right] != -1)
            return memo[left][right];
        int ret = INT_MAX; // 为了不影响结果，选最大值
        // 遍历区间内的每一个位置当做该层选择的位置
        for(int i = left; i <= right; i++)
        {
            int l = i + dfs(left, i - 1, memo);
            int r = i + dfs(i + 1, right, memo);
            // 找到所有选择中 最大值最小的
            ret = min(ret, max(l, r));
        }
        memo[left][right] = ret;
        return memo[left][right];
    }
    int getMoneyAmount(int n) 
    {
        vector<vector<int>> memo(n + 1, vector<int>(n + 1, -1));
        return dfs(1, n, memo);
    }
};

时间复杂度：$O(n^3)$
空间复杂度：$O(n^2)$

329. 矩阵中的最长递增路径

题目链接：https://leetcode.cn/problems/longest-increasing-path-in-a-matrix/description/

个人解

思路：

• 没啥好说的，常规暴搜 + 备忘录
• 不需要check数组，因为要求严格递增，所以天然无回路

用时：13:00
屎山代码：

class Solution {
public:
    int dx[4] = {0, 0, 1, -1};
    int dy[4] = {1, -1, 0, 0};
    int m, n;
    // 以 pos 位置为开始，然后返回以该位置为开始的最长路径
    int dfs(vector<vector<int>>& matrix, vector<vector<int>>& memo, int x, int y)
    {
        if(memo[x][y]) return memo[x][y];
        int ret = 1;
        for(int i = 0; i < 4; i++)
        {
            int nx = x + dx[i], ny = y + dy[i]; // 下一个位置
            if(nx < m && nx >= 0 && ny < n && ny >= 0 && matrix[x][y] < matrix[nx][ny])
                ret = max(ret, 1 + dfs(matrix, memo, nx, ny));
        }
        memo[x][y] = ret;
        return memo[x][y];
    }
    int longestIncreasingPath(vector<vector<int>>& matrix) {
        m = matrix.size(), n = matrix[0].size();
        vector<vector<int>> memo(m, vector<int>(n, 0));
        int ans = 0;
        for(int i = 0; i < m; i++)
        {
            for(int j = 0; j < n; j++)
                ans = max(ans, dfs(matrix, memo, i, j));
        }
        return ans;
    }
};

时间复杂度：$O(m\ast n)$
空间复杂度：$O(m\ast n)$

🌈我的分享也就到此结束啦🌈
要是我的分享也能对你的学习起到帮助，那简直是太酷啦！
若有不足，还请大家多多指正，我们一起学习交流！
📢公主，王子：点赞👍→收藏⭐→关注🔍
感谢大家的观看和支持！祝大家都能得偿所愿，天天开心！！！