dfs记忆化搜索刷题 + 总结

记忆化搜索 vs 动态规划

1. 记忆化搜索：有完全相同的问题/数据保存起来，带有备忘录的递归
2.记忆化搜索的步骤：
1、添加一个备忘录 <可变参数，返回值>
2、递归每次返回的时候，将结果放入备忘录中
3、在每次进入递归的时候，往备忘录中查找一下
3. 记忆化搜索和常规的动态规划都是动态规划，暴搜 -> 记忆化搜索 -> 动态规划
4. 有大量重复的问题才能改成记忆化搜索

斐波那契数

题目链接

题解

1. 创建一个备忘录
2. 把备忘录中的值初始化为斐波那契数中不可能出现的的值-1
3. 在每次递归完成之前，把值存入备忘录中
4. 在每次进入递归的时候，查找一下备忘录中是否有值，有值就直接返回，相当于剪枝

代码

class Solution 
{
public:// 记忆化搜索int memo[31];int fib(int n) {memset(memo,-1,sizeof memo);return dfs(n);}int dfs(int n){if(memo[n] != -1){return memo[n];}if(n == 0 || n == 1){memo[n] = n;return n;}memo[n] = dfs(n-1) + dfs(n-2);return memo[n];}
};// 动态规划
class Solution 
{
public:int dp[31];int fib(int n) {dp[0] = 0,dp[1] = 1;for(int i = 2;i <= n;i++){dp[i] = dp[i-1] + dp[i-2];}return dp[n];}
};

不同路径

题目链接

题解

1. 函数头的设计，只需要i和j的坐标
2. 返回条件：i == 0 || j == 0都是返回0
i == 1 && j == 1 第一个点返回1
3. 记忆化搜索就是创建一个二维的备忘录，在递归之前往备忘录中查找一下，返回之前把结果都存在备忘录中

代码

// 记忆化搜索
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];}
};

最长递增子序列

题目链接

题解

1. 记忆化搜索：每次枚举以pos位置为起点的最长递增子序列，让pos+1位置的值和pos位置比较大小，如果大于就加一，函数头需要nums和pos位置，函数体需要pos+1位置到n-1位置，dfs会完成找到最大递增子序列的工作，+1是加上本身
2. 动态规划：从后往前添加状态，第一个循环用来枚举位置，第二个循环用来比较大小，更新最长递增子序列到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();// 最短的子序列都是1vector<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

题目链接

题解

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

代码

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;}
};

矩阵中的最长递增路径

题目链接

题解

1. 算法原理：从一个点开始dfs，暴力枚举出每一个递增的路径，返回其中最长的路径即可
2. dfs函数的设计，需要i，j坐标去搜索每一个位置
3. 记忆化数组，如果出现相同的路径，不用再次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)