记忆化搜索篇

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

问题：

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

1. 斐波那契数

// 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();
}

2. 不同路径

// 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();
}

3. 最长递增子序列

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

4. 猜数字大小 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);
}

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

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