Commitcfd56a1

authored

Create 329-Longest-Increasing-Path-in-a-Matrix.java

1 parent28b4f29 commitcfd56a1Copy full SHA for cfd56a1

File tree

+37

-0

lines changed

+37

-0

lines changed

Lines changed: 37 additions & 0 deletions

Original file line number	Diff line number	Diff line change
`@@ -0,0 +1,37 @@`
	`1`	`+//Another similar problem: https://leetcode.com/contest/weekly-contest-300/problems/number-of-increasing-paths-in-a-grid/`
	`2`	`+`
	`3`	`+classSolution {`
	`4`	`+publicintlongestIncreasingPath(int[][]matrix) {`
	`5`	`+intm =matrix.length;`
	`6`	`+intn =matrix[0].length;`
	`7`	`+int[][]dp =newint[m][n];`
	`8`	`+for (intd[]:dp)`
	`9`	`+Arrays.fill(d, -1);`
	`10`	`+for (inti =0;i<m;i++) {`
	`11`	`+for (intj =0;j<n;j++) {`
	`12`	`+if (dp[i][j]==-1)`
	`13`	`+dfs(matrix,dp,m,n,i,j, -1);`
	`14`	`+ }`
	`15`	`+ }`
	`16`	`+intmax =Integer.MIN_VALUE;`
	`17`	`+for (int[]d:dp) {`
	`18`	`+for (inti:d)`
	`19`	`+max =Math.max(i,max);`
	`20`	`+ }`
	`21`	`+returnmax;`
	`22`	`+ }`
	`23`	`+`
	`24`	`+publicintdfs(int[][]matrix,int[][]dp,intm,intn,inti,intj,intparent) {`
	`25`	`+if (i>=m \|\|j>=n \|\|i<0 \|\|j<0 \|\|matrix[i][j]<=parent)`
	`26`	`+return0;`
	`27`	`+parent =matrix[i][j];`
	`28`	`+if (dp[i][j]!=-1)`
	`29`	`+returndp[i][j];`
	`30`	`+intleft =dfs(matrix,dp,m,n,i,j-1,parent);`
	`31`	`+intright =dfs(matrix,dp,m,n,i,j+1,parent);`
	`32`	`+intbottom =dfs(matrix,dp,m,n,i+1,j,parent);`
	`33`	`+inttop =dfs(matrix,dp,m,n,i-1,j,parent);`
	`34`	`+dp[i][j] =1+Math.max(Math.max(left,right),Math.max(top,bottom));`
	`35`	`+returndp[i][j];`
	`36`	`+ }`
	`37`	`+}`

Comments

(0)