【综合算法学习】（第二十篇）

目录

猜数字⼤⼩II（medium）

题目解析

讲解算法原理

编写代码

矩阵中的最⻓递增路径（hard）

题目解析

讲解算法原理

编写代码

---

猜数字⼤⼩II（medium）

题目解析

1.题目链接：. - 力扣（LeetCode）

2.题目描述

我们正在玩⼀个猜数游戏，游戏规则如下：
a. 我从1到n之间选择⼀个数字。b. 你来猜我选了哪个数字。
c. 如果你猜到正确的数字，就会赢得游戏。d. 如果你猜错了，那么我会告诉你，我选的数字⽐你的更⼤或者更⼩，并且你需要继续猜数。e. 每当你猜了数字x并且猜错了的时候，你需要⽀付⾦额为x的现⾦。如果你花光了钱，就会
输掉游戏。
给你⼀个特定的数字n，返回能够确保你获胜的最⼩现⾦数，不管我选择那个数字。

⽰例1：

输⼊：n=10输出：16
解释：制胜策略如下：• 数字范围是[1,10]。你先猜测数字为7。-如果这是我选中的数字，你的总费⽤为$0。否则，你需要⽀付$7。-如果我的数字更⼤，则下⼀步需要猜测的数字范围是[8,10]。你可以猜测数字为9。-如果这是我选中的数字，你的总费⽤为$7。否则，你需要⽀付$9。
-如果我的数字更⼤，那么这个数字⼀定是10。你猜测数字为10并赢得游戏，总费⽤为$7+$9=$16。
-如果我的数字更⼩，那么这个数字⼀定是8。你猜测数字为8并赢得游戏，总费⽤为$7+$9=$16。
-如果我的数字更⼩，则下⼀步需要猜测的数字范围是[1,6]。你可以猜测数字为3。-如果这是我选中的数字，你的总费⽤为$7。否则，你需要⽀付$3。
-如果我的数字更⼤，则下⼀步需要猜测的数字范围是[4,6]。你可以猜测数字为5。-如果这是我选中的数字，你的总费⽤为$7+$3=$10。否则，你需要⽀付$5。-如果我的数字更⼤，那么这个数字⼀定是6。你猜测数字为6并赢得游戏，总费⽤为$7+$3
+$5=$15。
-如果我的数字更⼩，那么这个数字⼀定是4。你猜测数字为4并赢得游戏，总费⽤为$7+$3+$5=$15。
-如果我的数字更⼩，则下⼀步需要猜测的数字范围是[1,2]。你可以猜测数字为1。-如果这是我选中的数字，你的总费⽤为$7+$3=$10。否则，你需要⽀付$1。-如果我的数字更⼤，那么这个数字⼀定是2。你猜测数字为2并赢得游戏，总费⽤为$7+$3
+$1=$11。
在最糟糕的情况下，你需要⽀付$16。因此，你只需要$16就可以确保⾃⼰赢得游戏。⽰例2：
输⼊：n=1
输出：0
解释：只有⼀个可能的数字，所以你可以直接猜1并赢得游戏，⽆需⽀付任何费⽤。⽰例3：
输⼊：n=2
输出：1
解释：有两个可能的数字1和2。
◦ 你可以先猜1。
-如果这是我选中的数字，你的总费⽤为$0。否则，你需要⽀付$1。-如果我的数字更⼤，那么这个数字⼀定是2。你猜测数字为2并赢得游戏，总费⽤为$1。最糟糕的情况下，你需要⽀付$1。

提⽰：
1<=n<=200

讲解算法原理

解法（暴搜->记忆化搜索）：
算法思路：
暴搜：
a. 递归含义：给 dfs ⼀个使命，给他⼀个区间 [left, right] ，返回在这个区间上能完胜
的最⼩费⽤；
b. 函数体：选择 [left, right] 区间上的任意⼀个数作为头结点，然后递归分析左右⼦树。
求出所有情况下的最⼩值；
c. 递归出⼝：当 left >= right 的时候，直接返回 0 。
记忆化搜索：
a. 加上⼀个备忘录；
b. 每次进⼊递归的时候，去备忘录⾥⾯看看；
c. 每次返回的时候，将结果加⼊到备忘录⾥⾯。

编写代码

c++算法代码：

class Solution
{int memo[201][201];
public: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, head + max(x, y));}memo[left][right] = ret;return ret;}
};

java算法代码：

class Solution
{int[][] memo;public int getMoneyAmount(int n) {memo = new int[n + 1][n + 1];return dfs(1, n);}public int dfs(int left, int right){if(left >= right) return 0;if(memo[left][right] != 0){return memo[left][right];}int ret = Integer.MAX_VALUE;for(int head = left; head <= right; head++){int x = dfs(left, head - 1);int y = dfs(head + 1, right);ret = Math.min(Math.max(x, y) + head, ret);}memo[left][right] = ret;return ret;}
}

矩阵中的最⻓递增路径（hard）

题目解析

1.题目链接：. - 力扣（LeetCode）

2.题目描述

给定⼀个mxn整数矩阵matrix，找出其中最⻓递增路径的⻓度。
对于每个单元格，你可以往上，下，左，右四个⽅向移动。你不能在对⻆线⽅向上移动或移动到边界外（即不允许环绕）。
⽰例1：

输⼊：matrix=[[9,9,4],[6,6,8],[2,1,1]]输出：4
解释：最⻓递增路径为[1,2,6,9]。

⽰例2：

输⼊：matrix=[[3,4,5],[3,2,6],[2,2,1]]输出：4
解释：最⻓递增路径是[3,4,5,6]。注意不允许在对⻆线⽅向上移动。⽰例3：
输⼊：matrix=[[1]]输出：1

提⽰：
m==matrix.length
n==matrix[i].length
1<=m,n<=200
0<=matrix[i][j]<=2^31-1

讲解算法原理

解法（暴搜->记忆化搜索）：
算法思路：
暴搜：
a. 递归含义：给 dfs ⼀个使命，给他⼀个下标 [i, j] ，返回从这个位置开始的最⻓递增路径
的⻓度；
b. 函数体：上下左右四个⽅向瞅⼀瞅，哪⾥能过去就过去，统计四个⽅向上的最⼤⻓度；c. 递归出⼝：因为我们是先判断再进⼊递归，因此没有出⼝~
记忆化搜索：
a. 加上⼀个备忘录；
b. 每次进⼊递归的时候，去备忘录⾥⾯看看；
c. 每次返回的时候，将结果加⼊到备忘录⾥⾯。

编写代码

c++算法代码：

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

java算法代码：

class Solution
{int m, n;int[] dx = {0, 0, 1, -1};int[] dy = {1, -1, 0, 0};int[][] memo;public int longestIncreasingPath(int[][] matrix) {m = matrix.length; n = matrix[0].length;memo = new int[m][n];int ret = 0;for(int i = 0; i < m; i++)for(int j = 0; j < n; j++)ret = Math.max(ret, dfs(matrix, i, j));return ret;}public int dfs(int[][] matrix, int i, int j){if(memo[i][j] != 0){return memo[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 < m && y >= 0 && y < n && matrix[x][y] > matrix[i]
[j]){ret = Math.max(ret, dfs(matrix, x, y) + 1);}}memo[i][j] = ret;return ret;}
}