Commit500ae42

committed

coin change 2

1 parent4005d49 commit500ae42Copy full SHA for 500ae42

File tree

+33

-1

lines changed

+33

-1

lines changed

Lines changed: 32 additions & 0 deletions

Original file line number	Diff line number	Diff line change
`@@ -0,0 +1,32 @@`
	`1`	`+use std::collections::HashMap;`
	`2`	`+pubstructSolution{}`
	`3`	`+implSolution{`
	`4`	`+pubfnchange(amount:i32,coins:Vec<i32>) ->i32{`
	`5`	`+letmut mem:HashMap<(usize,i32),i32> =HashMap::new();`
	`6`	`+Self::dfs(0,0, amount,&coins,&mut mem)`
	`7`	`+}`
	`8`	`+`
	`9`	`+fndfs(`
	`10`	`+sum:i32,`
	`11`	`+i:usize,`
	`12`	`+amount:i32,`
	`13`	`+coins:&Vec<i32>,`
	`14`	`+mem:&mutHashMap<(usize,i32),i32>,`
	`15`	`+) ->i32{`
	`16`	`+if sum > amount \|\| i >= coins.len(){`
	`17`	`+return0;`
	`18`	`+}`
	`19`	`+`
	`20`	`+if sum == amount{`
	`21`	`+return1;`
	`22`	`+}`
	`23`	`+`
	`24`	`+ifletSome(val) = mem.get(&(i, sum)){`
	`25`	`+return*val;`
	`26`	`+}`
	`27`	`+let val =Self::dfs(sum + coins[i], i, amount, coins, mem)`
	`28`	`+ +Self::dfs(sum, i +1, amount, coins, mem);`
	`29`	`+ mem.insert((i, sum), val);`
	`30`	`+ val`
	`31`	`+}`
	`32`	`+}`

Lines changed: 1 addition & 1 deletion

Comments

(0)