力扣300.最长递增子序列（经典dp)力扣375.猜数字II力扣.329矩阵最长的递增子序列力扣.33搜索旋转排序数组 - 详解

目录

 力扣300.最长递增子序列（经典dp)

力扣375.猜数字II

力扣.329矩阵最长的递增子序列

力扣.33搜索旋转排序数组

---

 力扣300.最长递增子序列（经典dp)

以xx为后缀的最长递增子序列

class Solution {
public int lengthOfLIS(int[] nums) {
int n=nums.length;
int[]dp=new int[n];
Arrays.fill(dp,1);
int max=1;
for(int i=1;inums[j])dp[i]=Math.max(dp[j]+1,dp[i]);
}
max=Math.max(dp[i],max);
}
return max;
}
}

力扣375.猜数字II

从[1-i-1] [i+1, 200]里面挑选， 里面不一定谁大谁小

x代表左边所有种情况的最小值，y表示右边的所有最小值

此时为什么要x,y的最大值呢   ，我在根节点处理的是最大情况，确保整个情况都是完胜，即左右都要获得胜利，不管你选什么，我的这个策略都是最好的，优秀的。

class Solution {
int[][]mono;
public int dfs(int l,int r){
//假如==2的时候，那么就是【1，1的区间】那么就这一个数，那就不需要花钱的
//即left==right的时候
if(l>=r)return 0;
if(mono[l][r]!=-1)return mono[l][r];
int min=0x3f3f3f3f;
for(int i=l;i<=r;i++){
//假如i==1的话 就不是合法区间
int x=dfs(l,i-1);
int y=dfs(i+1,r);
//为什么要统计x,y的最大值，因为我找到的是左边，右边满足赢整个游戏的值，因此是最大值
//他的统计左右节点，是不计算当前节点的值，当前节点的值，在下面被添加
min=Math.min(Math.max(x,y)+i,min);
}
mono[l][r]=min;
return min;
}
//最小金额，不是最小次数，因此二分并非最优，所以暴力枚举去判断
public int getMoneyAmount(int n) {
mono=new int[n+1][n+1];
for(int i=0;i

力扣.329矩阵最长的递增子序列

这个有点微微细节的记忆化搜索，跟bfs不同的是，第一个他不用存储是否走过，即vis,因为

不断递增，无需dfs，然后第二个dfs,最开始的值都必须要是1，因为即使没有任何一个值和他匹配递增的关系，他自己也是1个长度。

class Solution {
int[][]mono;
int[]dx={0,0,1,-1};
int[]dy={1,-1,0,0};
public int dfs(int i,int j,int[][] matrix){
int n=matrix.length;
int m=matrix[0].length;
if(mono[i][j]!=-1)return mono[i][j];
int count=0;
for(int k=0;k=0&&x=0&&ymatrix[i][j]){
count=Math.max(dfs(x,y,matrix)+1,count);
}
}
mono[i][j]=Math.max(count,1);
return mono[i][j];
}
public int longestIncreasingPath(int[][] matrix) {
int n=matrix.length;
int m=matrix[0].length;
mono=new int[n][m];
int max=0;
for(int i=0;i

力扣.33搜索旋转排序数组

A-B   :    nums[i]>nums[n-1]

C-D :      nums[i]<=nums[n-1]