记忆化搜索【下】

本文主要是介绍记忆化搜索【下】，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

375. 猜数字大小II

题目分析

题目链接：375. 猜数字大小 II - 力扣（LeetCode）

题目比较长，大致意思就是给一个数，比如说10，定的数字是7，让我们在[1, 10]这个区间猜。

如果猜大或猜小都会说明是大了还是小了，此外，我们还需要支付猜错数字对应的现金。

现在就是让我们定制一个猜测策略，确保准备最少的钱能猜对

如果采用二分查找，只能确保最小次数，题目要求的是最小金额

算法原理

随便选一个数i最为起始位置，如果不对就进入往下找：

1. 选小了：[1, i-1]
2. 选大了：[i+1,10]

从这里面继续选一个数作为“根节点”，这就出现了重复情况了：

• 给一个区间，选一个头，在左右子树里面找出最小值

当以i为根节点的时候，左右子树返回的值，选择较大值，因为确保在整个操作当中，都是完胜的。

代码实现

暴搜：

会超时

class Solution {
public:int getMoneyAmount(int n){return dfs(1, n);}int dfs(int left, int right){//left > right 此时区间不合法，选不出来//left == right 到叶子节点了，就是要选择的，选对不用支付if(left >= right){return 0;}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));}return ret;}
};

记忆化搜索：

出现重复情况，可采用记忆化搜索

class Solution {
public:int memo[201][201];int getMoneyAmount(int n){return dfs(1, n);}int dfs(int left, int right){//left > right 此时区间不合法，选不出来//left == right 到叶子节点了，就是要选择的，选对不用支付if(left >= right){return 0;}if(memo[left][right] != 0){return memo[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));}memo[left][right] = ret;return ret;}
};

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

题目链接：329. 矩阵中的最长递增路径

题目较短，就不分析了

算法原理

找个一个位置，上下左右开始试，如果有递增的，则走到下一个节点，然后又开始上下左右尝试，记录最长的情况

代码实现

暴搜会超时，记忆化搜索加一个备忘录即可

class Solution {
public:int memo[201][201];int dx[4] = {1, -1, 0, 0};int dy[4] = {0, 0, 1, -1};vector<vector<int>> matrix;int m, n;int longestIncreasingPath(vector<vector<int>>& _matrix){matrix = _matrix;int ret = 0;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(i, j));}}return ret;}int dfs(int i, int j){if(memo[i][j] != 0){return memo[i][j];}int path = 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]){path = max(path, dfs(x, y)+1);}}memo[i][j] = path;return path;}
};

这篇关于记忆化搜索【下】的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---