[Algorithm][回溯][记忆化搜索][最长递增子序列][猜数字大小Ⅱ][矩阵中的最长递增路径]详细讲解

发布于：2024-05-25 ⋅ 阅读:(136) ⋅ 点赞:(0)

目录

1.最长递增子序列

1.题目链接

2.算法原理详解

  • 题目解析：从每个位置，依次计算其最长递增子序列
    请添加图片描述

  • 思路选择：

    • 暴搜(递归) -> 本题会超时:P
    • 记忆化搜索
    • 动态规划

  • 尝试：暴搜 -> 记忆化搜索 -> 动态规划

  • 暴搜：

    • DFS()设计：int DFS(nums, pos) -> 每次从pos位置找最长递增子序列
    • 函数体：依次从pos位置往后枚举，更新本次最长递增子序列

  • 本题有大量重复要计算的值，故可以用记忆化搜索

  • 记忆化搜索：

    • 备忘录：vector<int> mem
    • 返回之前，把结果存在备忘录中
    • 递归之前，查找一下备忘录是否有要找的值

  • 动态规划

    • 注意：本题是前面的值依赖后面的值，所以**填表顺序要从后往前填**

3.代码实现

// v1.0 暴搜
class Solution 
{
public:
    int lengthOfLIS(vector<int>& nums) 
    {
        int ret = 0;
        for(int i = 0; i < nums.size(); i++)
        {
            ret = max(ret, DFS(nums, i));
        }

        return ret;
    }

    int DFS(vector<int>& nums, int pos)
    {
        int ret = 1; // 细节：初值为1

        for(int i = pos + 1; i < nums.size(); i++)
        {
            if(nums[i] > nums[pos])
            {
                ret = max(ret, DFS(nums, i) + 1);    
            }
        }

        return ret;
    }
};
-------------------------------------------------------------------------------
// v2.0 记忆化搜索
class Solution 
{
    vector<int> mem;
public:
    int lengthOfLIS(vector<int>& nums) 
    {
        mem.resize(nums.size());

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

        return ret;
    }

    int DFS(vector<int>& nums, int pos)
    {
        if(mem[pos] != 0)
        {
            return mem[pos];
        }

        int ret = 1; // 细节：初值为1
        for(int i = pos + 1; i < nums.size(); i++)
        {
            if(nums[i] > nums[pos])
            {
                ret = max(ret, DFS(nums, i) + 1);    
            }
        }

        mem[pos] = ret;
        return ret;
    }
};
-------------------------------------------------------------------------------
// v3.0 动态规划
int lengthOfLIS(vector<int>& nums) 
{
    int n = nums.size();
    vector<int> dp(n, 1);

    int ret = 0;
    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;
}

2.猜数字大小 II

1.题目链接

2.算法原理详解

  • 题目思路解析：

    • 每次给出一个数据范围，从中找出花费最少的一次
    • 但是当一个结点的左右子树返回时，要取最大的，因为要确保"能获胜的最小金额"，就要让左右子树的两种情况都能实现
    • 最优解：取最小是在该范围内，每个数对应的最终结果取最小
      请添加图片描述

  • 思路选择：

    • 暴搜(递归) -> 本题会超时:P
    • 记忆化搜索

  • 暴搜：

    • DFS()设计：int DFS(int left, int right) -> 每次从[left, right]区间内找出最小的
    • 函数体：依次遍历[left, right]中的各个数，递归分析左右⼦树，求出所有情况下的最⼩值
    • 递归出口：
      • left > right：区间不存在，返回0
      • left == right：就是最后的一个结果，此时无需花钱，返回0

  • 本题有大量重复要计算的值，故可以用记忆化搜索
    请添加图片描述

  • 记忆化搜索：

    • 备忘录：vector<int> mem
    • 返回之前，把结果存在备忘录中
    • 递归之前，查找一下备忘录是否有要找的值

3.代码实现

// v1.0 暴搜
class Solution 
{
public:
    int getMoneyAmount(int n) 
    {
        return DFS(1, n);
    }

    int DFS(int left, int right)
    {
        if(left >= right)
        {
            return 0;
        }

        int ret = INT_MAX;
        for(int i = left; i <= right; i++) // 选择头结点
        {
            int x = DFS(left, i - 1);
            int y = DFS(i + 1, right);
            ret = min(ret, max(x, y) + i);
        }

        return ret;
    }
};
------------------------------------------------------------------------
// v2.0 记忆化搜索
class Solution 
{
    vector<vector<int>> mem;
public:
    int getMoneyAmount(int n) 
    {
        mem.resize(n + 1, vector(n + 1, 0));
        return DFS(1, n);
    }

    int DFS(int left, int right)
    {
        if(left >= right)
        {
            return 0;
        }

        if(mem[left][right] != 0)
        {
            return mem[left][right];
        }


        int ret = INT_MAX;
        for(int i = left; i <= right; i++) // 选择头结点
        {
            int x = DFS(left, i - 1);
            int y = DFS(i + 1, right);
            ret = min(ret, max(x, y) + i);
        }

        mem[left][right] = ret;
        return ret;
    }
};

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

1.题目链接

2.算法原理详解

  • 题目解析：遍历数组，对每个位置来一次DFS即可
  • 思路选择：
    • 暴搜(递归) -> 本题会超时:P
    • 记忆化搜索
  • 本题有大量重复要计算的值，故可以用记忆化搜索
    请添加图片描述

3.代码实现

// v1.0 暴搜
class Solution 
{
    int n, m;

    // "方向"向量数组
    int dx[4] = {1, -1, 0, 0};
    int dy[4] = {0, 0, 1, -1};
public:
    int longestIncreasingPath(vector<vector<int>>& matrix) 
    {
        n = matrix.size(), m = matrix[0].size();

        int ret = 0;
        for(int i = 0; i < n; i++)
        {
            for(int j = 0; j < m; j++)
            {
                ret = max(ret, DFS(matrix, i, j));
            }
        }

        return ret;
    }

    int DFS(vector<vector<int>>& matrix, int i, int j)
    {
        int ret = 1;
        for(int k = 0; k < 4; k++)
        {
            int x = i + dx[k], y = j + dy[k];
            if(x >= 0 && x < n && y >= 0 && y < m && matrix[x][y] > matrix[i][j])
            {
                ret = max(ret, DFS(matrix, x, y) + 1);
            }
        }

        return ret;
    }
};
---------------------------------------------------------------------------
// v2.0 记忆化搜索
class Solution 
{
    int n, m;
    vector<vector<int>> mem;

    // "方向"向量数组
    int dx[4] = {1, -1, 0, 0};
    int dy[4] = {0, 0, 1, -1};
public:
    int longestIncreasingPath(vector<vector<int>>& matrix) 
    {
        n = matrix.size(), m = matrix[0].size();
        mem.resize(n, vector<int>(m, 0));

        int ret = 0;
        for(int i = 0; i < n; i++)
        {
            for(int j = 0; j < m; j++)
            {
                ret = max(ret, DFS(matrix, i, j));
            }
        }

        return ret;
    }

    int DFS(vector<vector<int>>& matrix, int i, int j)
    {
        if(mem[i][j] != 0)
        {
            return mem[i][j];
        }
        int ret = 1;
        for(int k = 0; k < 4; k++)
        {
            int x = i + dx[k], y = j + dy[k];
            if(x >= 0 && x < n && y >= 0 && y < m && matrix[x][y] > matrix[i][j])
            {
                ret = max(ret, DFS(matrix, x, y) + 1);
            }
        }

        return mem[i][j] = ret;
    }
};

网站公告

今日签到

点亮在社区的每一天
去签到

热门文章

最新发布