Commit77af493

authored

Update 0279-perfect-squares.java

1 parentedcdfa7 commit77af493Copy full SHA for 77af493

File tree

+20

-0

lines changed

+20

-0

lines changed

Lines changed: 20 additions & 0 deletions

Original file line number	Diff line number	Diff line change
`@@ -1,3 +1,23 @@`
	`1`	`+classSolution {`
	`2`	`+publicintnumSquares(intn) {`
	`3`	`+int[]dp =newint[n+1];`
	`4`	`+Arrays.fill(dp,n);`
	`5`	`+dp[0] =0;`
	`6`	`+`
	`7`	`+for(inttarget =0;target <n +1;target++){`
	`8`	`+for(ints =0;s <target;s++){`
	`9`	`+intsquare =s*s;`
	`10`	`+if(target -square <0)`
	`11`	`+break;`
	`12`	`+dp[target] =Math.min(dp[target],1 +dp[target -square]);`
	`13`	`+ }`
	`14`	`+ }`
	`15`	`+returndp[n];`
	`16`	`+ }`
	`17`	`+}`
	`18`	`+`
	`19`	`+/---------------------------------------------------------------------------------------------------------------------------------------------------------/`
	`20`	`+`
`1`	`21`	`//This is a BFS based approach.`
`2`	`22`	`//We can also do this problem similar to coin change but the Time and space complexity will remain same (Just an extra queue in this one stil linear space).`
`3`	`23`

Comments

(0)