// Problem Ġstatement Ċ // ĠYou Ġare Ġgiven Ġcoins Ġof Ġdifferent Ġdenom inations Ġand Ġa Ġtotal Ġamount Ġof Ġmoney Ġamount . Ċ // ĠWrite Ġa Ġfunction Ġto Ġcompute Ġthe Ġfew est Ġnumber Ġof Ġcoins Ġthat Ġyou Ġneed Ġto Ġmake Ġup Ġthat Ġamount . Ċ // ĠIf Ġthat Ġamount Ġof Ġmoney Ġcannot Ġbe Ġmade Ġup Ġby Ġany Ġcombination Ġof Ġthe Ġcoins , Ġreturn Ġ- 1 . Ċ package Ġorg . algorithm . problems Ċ Ċ class Ġ` 0 0 6 4 _ coin _ change ` Ġ{ ĊĠĠĠ Ġfun Ġcoin Change ( coins : ĠInt Array , Ġamount : ĠInt ): ĠInt Ġ{ ĊĠĠĠĠĠĠĠ Ġcoins . sort () ĊĠĠĠĠĠĠĠ Ġvar Ġdp : ĠInt Array Ġ= ĠInt Array ( amount Ġ+ Ġ 1 ) Ġ{ Ġi Ġ-> Ġ- 1 Ġ} ĊĠĠĠĠĠĠĠ Ġdp [ 0 ] Ġ= Ġ 0 ; ĊĊĠĠĠĠĠĠĠ Ġfor Ġ( value Ġin Ġ 1 .. amount ) Ġ{ ĊĊĠĠĠĠĠĠĠĠĠĠĠ Ġvar Ġindex : ĠInt Ġ= Ġ 0 ĊĠĠĠĠĠĠĠĠĠĠĠ Ġvar Ġmin Quant Change : ĠInt Ġ= Ġ- 1 ĊĠĠĠĠĠĠĠĠĠĠĠ Ġwhile Ġ( index Ġ< Ġcoins . size Ġ&& Ġcoins [ index ] Ġ<= Ġvalue ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( dp [ value Ġ- Ġcoins [ index ]] Ġ!= Ġ- 1 ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( min Quant Change Ġ== Ġ- 1 ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġmin Quant Change Ġ= Ġdp [ value Ġ- Ġcoins [ index ]] Ġ+ Ġ 1 ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġelse ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġmin Quant Change Ġ= Ġmin Of ( min Quant Change , Ġdp [ value Ġ- Ġcoins [ index ]] Ġ+ Ġ 1 ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġindex ++ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĊĠĠĠĠĠĠĠĠĠĠĠ Ġdp [ value ] Ġ= Ġmin Quant Change ĊĠĠĠĠĠĠĠ Ġ} ĊĊĠĠĠĠĠĠĠ Ġreturn Ġdp . last (); ĊĠĠĠ Ġ} Ċ }