[Lc6_记忆化搜索] 最长递增子序列 | 矩阵中的最长递增路径

目录

1.最长递增子序列

题解

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

题解

---

1.最长递增子序列

链接：300. 最长递增子序列

给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。

子序列 是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。

示例 1：

输入：nums = [10,9,2,5,3,7,101,18]
输出：4
解释：最长递增子序列是 [2,3,7,101]，因此长度为 4 。

示例 2：

输入：nums = [0,1,0,3,2,3]
输出：4

示例 3：

输入：nums = [7,7,7,7,7,7,7]
输出：1

---

题解

子序列是数组中可以不连续的的序列。

• 让找的是最长的子序列。
• 最长子序列不止一个但是返回的是最长的长度。

还是用记忆化搜索方式，分两步，第一步 暴搜，第二步 暴搜->记忆化搜索

暴搜

如何暴力的把最长递增子序列长度找出来

• 其实我们能够暴力的把所有递增子序列找到然后找到其中最长的长度不就可以了。
• 如何暴力，很简单画个决策树，最长子序列可能回一任何一个起点开始
• 所以刚开始可能以2、5、3、7、101、18所有情况为起点
• 然后递归下去，如从2递归下去，只能从2后面的元素考虑，注意只能选择比2大的。

选择5然后从5递归下去，只能选择比5大的等等。（以递增为限制条件）

接下来思考一下这个递归函数如何设计

函数头 我们看我们每次都是干的什么事情

• 每次我们都以某个位置为起点，找到以这个起点开始的最长递增子序列的长度。
• int dfs(pos)，函数体 来一个for循环，让i从pos+1位置开始循环一直到n，因为考虑以pos位置为起点，接下来考虑的是pos+1位置，然后找到所有情况的最大值，然后在加上一个1就可以了
• 因为当前位置也要算上！

for(int i=pos+1; i<n;++i) max(dfs(i)+1)。

递归出口 不需要递归出口，把所有情况走完就返回了。

会超时间限制

class Solution {public:int lengthOfLIS(vector<int>& nums) {int n=nums.size();int ret=0;for(int i = 0; i < n; ++i){ret=max(ret,dfs(nums,i));}return ret;}int dfs(vector<int>& nums, int pos){int ret=1;//!!!!! 必须等于1,如果pos是最后一个,循环进不去,但它也是一个子序列,返回1才对.for(int i = pos + 1; i < nums.size(); ++i){if(nums[i] > nums[pos])ret=max(ret,dfs(nums,i)+1);}return ret;}
};

 int ret=1;
    //!!!!! 必须等于1,如果pos是最后一个,循环进不去,但它也是一个子序列,返回1才对. 

暴搜->记忆化搜索
存在大量完全相同的问题，可以改成记忆化搜索
 

还是那三步，这里就不写了。这里备忘录用的是局部的也是可以的。

• 根据搜索，我们可以发现
• 其实你走哪一条分支，我根本就不关心
• 让计算机所有情况遍历的搜下去
• 我只关心搜下去之后，我拿到的是返回值下面 我能走到的 最长的一条路径长度
• 我处理的手法就是走到了 满足条件的 就return 时标记加1，再继续往下走~

class Solution {public:
vector<int> memo;int lengthOfLIS(vector<int>& nums) {int n=nums.size();memo.resize(n,0);int ret=0;for(int i = 0; i < n; ++i){ret=max(ret,dfs(nums,i));}return ret;}int dfs(vector<int>& nums, int pos){if(memo[pos]) return memo[pos];int ret=1;//!!!!! 必须等于1,如果pos是最后一个,循环进不去,但它也是一个子序列,返回1才对.for(int i = pos + 1; i < nums.size(); ++i){if(nums[i] > nums[pos])ret=max(ret,dfs(nums,i)+1);}memo[pos]=ret;return ret;  //返回 多个选择的max  ，+1是在return路径长度上 实现的}
};

记忆化搜索->动态规划

这里动态规划代码和之前的有点不一样。

首先来一个dp表，dfs函数->状态表示：dp[i]表示以i位置为起点的最长递增子序列长度。

• 函数体-> 状态转移方程 ：当求pos这个位置的时候，依赖的是pos后面的值，从里面找到最大然后在加+1。
• 因此这个dp表填表顺序其实是从后往前填表。
• 初始化都为1，自己本身也是一个子序列。
• 返回值 返回的是dp表中最大值。

---

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

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

给定一个 m x n 整数矩阵 matrix ，找出其中 最长递增路径 的长度。

对于每个单元格，你可以往上，下，左，右四个方向移动。 你 不能 在 对角线 方向上移动或移动到 边界外（即不允许环绕）。

---

题解

给一个mxn的矩阵，里面有很多递增序列，返回里面递增序列的最长长度。

暴搜

让找最长递增序列长度，那就暴力枚举所有递增序列从中选择最长的。

• 从第一个位置开始走，上下左右去找，然后返回这个位置上下左右中最长的，记住还要加自己本身1个。
• 比如从1开始有2和6两种走法，从6返回的是2加起点最长递增是4，从2返回的是3加起来最长递增长度是4，所有1这个位置最长递增是4。

然后还要和其他位置比，选择最长的。

暴搜->记忆化搜索
从1到6搜索和从6开始的 最优搜索情况都是一样的。因此可以改成记忆化搜索。

class Solution {
public:int dx[4]={0,0,1,-1};int dy[4]={1,-1,0,0};int m,n;vector<vector<int>> memo;int longestIncreasingPath(vector<vector<int>>& matrix) {m=matrix.size();n=matrix[0].size();int count=0;memo.resize(m,vector<int>(n,0));for(int i=0;i<m;i++){for(int j=0;j<n;j++){memo[i][j]=dfs(matrix,i,j);count=max(count,memo[i][j]);}}return count;}int dfs(vector<vector<int>>& matrix,int i,int j){if(memo[i][j]) 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;// //返回 四个方向选择的max  ，+1是在return路径长度上 实现的} 
};

  int ret=1;  //在for前初始化
    //!!!!! 必须等于1,如果pos是最后一个,循环进不去,但它也是一个子序列,返回1才对. 

爆搜，满足条件 就继续搜，这很计算机~

• 多加一层搜， 就多return一个 1 的计数， return 通过Max选择  返回该点最长路径