目录
- 1.最长递增子序列
- 1.题目链接
- 2.算法原理详解
- 3.代码实现
- 2.猜数字大小 II
- 1.题目链接
- 2.算法原理详解
- 3.代码实现
- 3.矩阵中的最长递增路径
- 1.题目链接
- 2.算法原理详解
- 3.代码实现
1.最长递增子序列
1.题目链接
- 最长递增子序列
2.算法原理详解
-
题目解析：从每个位置，依次计算其最长递增子序列
-
思路选择：
- 暴搜(递归) -> 本题会超时:P
- 记忆化搜索
- 动态规划
-
尝试：暴搜 -> 记忆化搜索 -> 动态规划
-
暴搜：
DFS()设计：int DFS(nums, pos)-> 每次从pos位置找最长递增子序列- 函数体：依次从
pos位置往后枚举，更新本次最长递增子序列
-
本题有大量重复要计算的值，故可以用记忆化搜索
-
记忆化搜索：
- 备忘录：
vector<int> mem - 返回之前，把结果存在备忘录中
- 递归之前，查找一下备忘录是否有要找的值
- 备忘录：
-
动态规划
- 注意：本题是前面的值依赖后面的值，所以**填表顺序要从后往前填**
3.代码实现
// v1.0 暴搜
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; // 细节：初值为1
for(int i = pos + 1; i < nums.size(); i++)
{
if(nums[i] > nums[pos])
{
ret = max(ret, DFS(nums, i) + 1);
}
}
return ret;
}
};
-------------------------------------------------------------------------------
// v2.0 记忆化搜索
class Solution
{
vector<int> mem;
public:
int lengthOfLIS(vector<int>& nums)
{
mem.resize(nums.size());
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)
{
if(mem[pos] != 0)
{
return mem[pos];
}
int ret = 1; // 细节：初值为1
for(int i = pos + 1; i < nums.size(); i++)
{
if(nums[i] > nums[pos])
{
ret = max(ret, DFS(nums, i) + 1);
}
}
mem[pos] = ret;
return ret;
}
};
-------------------------------------------------------------------------------
// v3.0 动态规划
int lengthOfLIS(vector<int>& nums)
{
int n = nums.size();
vector<int> dp(n, 1);
int ret = 0;
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;
}
2.猜数字大小 II
1.题目链接
- 猜数字大小 II
2.算法原理详解
-
题目思路解析：
- 每次给出一个数据范围，从中找出花费最少的一次
- 但是当一个结点的左右子树返回时，要取最大的，因为要确保"能获胜的最小金额"，就要让左右子树的两种情况都能实现
- 最优解：取最小是在该范围内，每个数对应的最终结果取最小
-
思路选择：
- 暴搜(递归) -> 本题会超时:P
- 记忆化搜索
-
暴搜：
DFS()设计：int DFS(int left, int right)-> 每次从[left, right]区间内找出最小的- 函数体：依次遍历
[left, right]中的各个数，递归分析左右⼦树，求出所有情况下的最⼩值 - 递归出口：
left > right：区间不存在，返回0left == right：就是最后的一个结果，此时无需花钱，返回0
-
本题有大量重复要计算的值，故可以用记忆化搜索
-
记忆化搜索：
- 备忘录：
vector<int> mem - 返回之前，把结果存在备忘录中
- 递归之前，查找一下备忘录是否有要找的值
- 备忘录：
3.代码实现
// v1.0 暴搜
class Solution
{
public:
int getMoneyAmount(int n)
{
return DFS(1, n);
}
int DFS(int left, int right)
{
if(left >= right)
{
return 0;
}
int ret = INT_MAX;
for(int i = left; i <= right; i++) // 选择头结点
{
int x = DFS(left, i - 1);
int y = DFS(i + 1, right);
ret = min(ret, max(x, y) + i);
}
return ret;
}
};
------------------------------------------------------------------------
// v2.0 记忆化搜索
class Solution
{
vector<vector<int>> mem;
public:
int getMoneyAmount(int n)
{
mem.resize(n + 1, vector(n + 1, 0));
return DFS(1, n);
}
int DFS(int left, int right)
{
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 x = DFS(left, i - 1);
int y = DFS(i + 1, right);
ret = min(ret, max(x, y) + i);
}
mem[left][right] = ret;
return ret;
}
};
3.矩阵中的最长递增路径
1.题目链接
- 矩阵中的最长递增路径
2.算法原理详解
- 题目解析：遍历数组，对每个位置来一次DFS即可
- 思路选择：
- 暴搜(递归) -> 本题会超时:P
- 记忆化搜索
- 本题有大量重复要计算的值，故可以用记忆化搜索
3.代码实现
// v1.0 暴搜
class Solution
{
int n, m;
// "方向"向量数组
int dx[4] = {1, -1, 0, 0};
int dy[4] = {0, 0, 1, -1};
public:
int longestIncreasingPath(vector<vector<int>>& matrix)
{
n = matrix.size(), m = matrix[0].size();
int ret = 0;
for(int i = 0; i < n; i++)
{
for(int j = 0; j < m; j++)
{
ret = max(ret, DFS(matrix, i, j));
}
}
return ret;
}
int DFS(vector<vector<int>>& matrix, int i, int j)
{
int ret = 1;
for(int k = 0; k < 4; k++)
{
int x = i + dx[k], y = j + dy[k];
if(x >= 0 && x < n && y >= 0 && y < m && matrix[x][y] > matrix[i][j])
{
ret = max(ret, DFS(matrix, x, y) + 1);
}
}
return ret;
}
};
---------------------------------------------------------------------------
// v2.0 记忆化搜索
class Solution
{
int n, m;
vector<vector<int>> mem;
// "方向"向量数组
int dx[4] = {1, -1, 0, 0};
int dy[4] = {0, 0, 1, -1};
public:
int longestIncreasingPath(vector<vector<int>>& matrix)
{
n = matrix.size(), m = matrix[0].size();
mem.resize(n, vector<int>(m, 0));
int ret = 0;
for(int i = 0; i < n; i++)
{
for(int j = 0; j < m; j++)
{
ret = max(ret, DFS(matrix, i, j));
}
}
return ret;
}
int DFS(vector<vector<int>>& matrix, int i, int j)
{
if(mem[i][j] != 0)
{
return mem[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 < n && y >= 0 && y < m && matrix[x][y] > matrix[i][j])
{
ret = max(ret, DFS(matrix, x, y) + 1);
}
}
return mem[i][j] = ret;
}
};
