【递归深搜之记忆化搜索算法】
1. 斐波那契数
解法一：递归
class Solution {
public:int fib(int n) {return dfs(n);}int dfs(int n){if(n == 0 || n == 1)return n;return dfs(n - 1) + dfs(n - 2);}
};解法二：记忆化搜索
class Solution {int nums[31]; // 备忘录
public:int fib(int n) {memset(nums, -1, sizeof(nums)); // 全部都初始化为-1return dfs(n);}int dfs(int n){// 在备忘录里面查询一下if(nums[n] != -1){// 如果已经计算过直接返回return nums[n];}// 否则在返回的时候添加到备忘录if(n == 0 || n == 1){nums[n] = n;return nums[n];}else{nums[n] = dfs(n - 1) + dfs(n - 2);return nums[n];} }
}; 解法三：动态规划
class Solution {int dp[31];
public: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]; // 返回值}
};
2. 不同路径
这个题目我们首先想到就是递归深搜右和下两个方向的路径，直到达到终点，此时我们统计次数，但是别忘记了要恢复现场哟
class Solution {int dx[2] = {0, 1};int dy[2] = {1, 0};bool vis[101][101] = { false };int ret;public:int uniquePaths(int m, int n) {dfs(0, 0, m, n);return ret;}void dfs(int i, int j, int m, int n){vis[i][j] = true;if(i == n - 1 && j == m - 1) // 注意这里 j 和 m 的位置{ret++;vis[i][j] = false; // 回溯：恢复访问状态return;}for(int k = 0 ; k < 2; k++){int x = dx[k] + i;int y = dy[k] + j;if(x >= 0 && x < n && y >=0 && y < m && !vis[x][y]) // 注意这里 x 和 y 的范围检查{dfs(x, y, m, n); // 传递正确的 m 和 nvis[x][y] = false; // 回溯：恢复访问状态}}}
};但是我们点击运行发现程序报错了，超时了，因为我们题目存在大量的重复的递归，所以我们这个题目需要采用记忆化手搜索去解决。
class Solution {
public:int uniquePaths(int m, int n) {return dfs(m, n);}int dfs(int i, int j){if(i == 0 || j == 0) return 0;if(i == j && j == 1) return 1;return dfs(i - 1, j) + dfs(i, j - 1);}
};
class Solution {
public:int uniquePaths(int m, int n) {// 添加备忘录vector<vector<int>> nums(m + 1, vector<int>(n + 1));return dfs(m, n, nums);}int dfs(int i, int j, vector<vector<int>>& nums){ // 查找备忘录if(nums[i][j]){return nums[i][j];}if(i == 0 || j == 0){// 因为数组原本内容就是0,这里就不用填写到备忘录return 0;}if(i == j && j == 1){nums[i][j] = 1;return nums[i][j];} nums[i][j] = dfs(i - 1, j, nums) + dfs(i, j - 1, nums);return nums[i][j];}
};同时我们这里还可以直接修改成动态规划的形式
class Solution {
public:int uniquePaths(int m, int n) {// 添加dp表vector<vector<int>> dp(m + 1, vector<int>(n + 1));// 因为数组原本内容就是0,这里就不用填写到dp表中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];}
};3. 最长递增子序列
我们看到这个题目，依然是先画出我们的决策树，先来看看决策树什么样子
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; // 起始位置算一个子序列for(int i = pos + 1; i < nums.size(); i++){if(nums[pos] < nums[i]){ret = max(ret, dfs(nums, i) + 1);}}return ret;}
};但是此时会超时，我们依然要使用记忆化搜索去解决。
class Solution {
public:int lengthOfLIS(vector<int>& nums) {vector<int> mem(nums.size());int ret = 0;for(int i = 0; i < nums.size(); i++){// 考虑以所有位置为起点的情况ret = max(ret, dfs(nums, i, mem));}return ret; }int dfs(vector<int>& nums, int pos, vector<int>& mem){// 查找备忘录if(mem[pos])return mem[pos];int ret = 1; // 起始位置算一个子序列for(int i = pos + 1; i < nums.size(); i++){if(nums[pos] < nums[i]){// 递归下一层,并且记录上当层子序列ret = max(ret, dfs(nums, i, mem) + 1);}}// 添加到备忘录mem[pos] = ret;return mem[pos];}
};此时我们也可以改成动态规划的代码
class Solution {
public:int lengthOfLIS(vector<int>& nums) {// dp(i) 表示以i位置为起点的最长递增子序列的个数// 填表顺序 -> 从后往前vector<int> dp(nums.size(), 1);int ret = 0;for(int i = nums.size() - 1; i >= 0; i--){for(int j = i + 1; j < nums.size(); j++){if(nums[j] > nums[i]){dp[i] = max(dp[i], dp[j] + 1);}}ret = max(dp[i], ret);}return ret; }
};4. 猜数字大小II
class Solution {int mem[201][201];
public:int getMoneyAmount(int n) {return dfs(1, n);}int dfs(int left, int right){if(left > right){return 0;}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 l = dfs(left, i - 1);int r = dfs(i + 1, right);ret = min(ret, i + max(l,r));}mem[left][right] = ret;return mem[left][right];}
};5. 矩阵中的最长递增路径
class Solution {int dx[4] = {0, 0, 1, -1};int dy[4] = {1, -1, 0, 0};int m, n;int nums[201][201];
public:int longestIncreasingPath(vector<vector<int>>& matrix) {m = matrix.size();n = matrix[0].size();int ret = 0;for(int i = 0; i < m; i++)for(int j = 0; j < n; j++)// 找到最大值 ret = max(ret, dfs(matrix, i, j));return ret;}int dfs(vector<vector<int>>& matrix, int i, int j){if(nums[i][j] != 0)return nums[i][j];int step = 1;for(int k = 0; k < 4; k++){int x = i + dx[k];int y = j + dy[k];if(x >= 0 && x < m && y >= 0 && y < n && matrix[x][y] > matrix[i][j]){step = max(step, dfs(matrix, x, y) + 1);}}nums[i][j] = step;return step;}
};