Commitfd22564

authored

Create 2140-solving-questions-with-brainpower.kt

1 parent355226b commitfd22564Copy full SHA for fd22564

File tree

+62

-0

lines changed

+62

-0

lines changed

Lines changed: 62 additions & 0 deletions

Original file line number	Diff line number	Diff line change
`@@ -0,0 +1,62 @@`
	`1`	`+/*`
	`2`	`+* DFS/Recursion + Memoization`
	`3`	`+*/`
	`4`	`+classSolution {`
	`5`	`+funmostPoints(questions:Array<IntArray>):Long {`
	`6`	`+val memo=LongArray(questions.size) {-1L }`
	`7`	`+`
	`8`	`+fundfs(i:Int):Long {`
	`9`	`+if (i>= questions.size)`
	`10`	`+return0`
	`11`	`+if (memo[i]!=-1L)`
	`12`	`+return memo[i]`
	`13`	`+`
	`14`	`+ memo[i]= maxOf(`
	`15`	`+ questions[i][0]+ dfs(i+1+ questions[i][1]),`
	`16`	`+ dfs(i+1)`
	`17`	`+ )`
	`18`	`+`
	`19`	`+return memo[i]`
	`20`	`+ }`
	`21`	`+`
	`22`	`+return dfs(0)`
	`23`	`+ }`
	`24`	`+}`
	`25`	`+`
	`26`	`+/*`
	`27`	`+* DP`
	`28`	`+*/`
	`29`	`+classSolution {`
	`30`	`+funmostPoints(q:Array<IntArray>):Long {`
	`31`	`+val n= q.lastIndex`
	`32`	`+val dp=LongArray(q.size)`
	`33`	`+`
	`34`	`+for (iin n downTo0) {`
	`35`	`+ dp[i]= maxOf(`
	`36`	`+if (i< n) dp[i+1]else0,`
	`37`	`+ q[i][0]+if (i+1+ q[i][1]<= n) dp[i+1+ q[i][1]]else0`
	`38`	`+ )`
	`39`	`+ }`
	`40`	`+`
	`41`	`+return dp[0]`
	`42`	`+ }`
	`43`	`+}`
	`44`	`+`
	`45`	`+/*`
	`46`	`+* DP with HashMap instead of Array for simpler code`
	`47`	`+*/`
	`48`	`+classSolution {`
	`49`	`+funmostPoints(q:Array<IntArray>):Long {`
	`50`	`+val n= q.lastIndex`
	`51`	`+val dp=HashMap<Int,Long>()`
	`52`	`+`
	`53`	`+for (iin n downTo0) {`
	`54`	`+ dp[i]= maxOf(`
	`55`	`+ dp[i+1]?:0L,`
	`56`	`+ q[i][0]+ (dp[i+1+ q[i][1]]?:0L)`
	`57`	`+ )`
	`58`	`+ }`
	`59`	`+`
	`60`	`+return dp[0]?:0L`
	`61`	`+ }`
	`62`	`+}`

Comments

(0)