| 2 | |
| 3 | //允许的钱是50，100,500，1000,5000 |
| 4 | var getMoney = function( number) { |
| 5 | if(!number) return 0 |
| 6 | const coins = [5000,1000,500,100,50] |
| 7 | const obj = { '50': 0, '100': 0, '500': 0, '1000': 0, '5000': 0 } |
| 8 | // obj通过计算得来通用 |
| 9 | // const obj = coins.reduce((ret,a)=>{ |
| 10 | // ret[a] = 0 |
| 11 | // return ret |
| 12 | // },{}) |
| 13 | let dp = Array(number+1).fill(Infinity) |
| 14 | dp[0] = 0 |
| 15 | let selected = Array(number+1) |
| 16 | selected[0] = {...obj} |
| 17 | for(const coin of coins){ |
| 18 | for(let j=coin;j<=number;j++){ |
| 19 | // dp[j] 都是Infinity |
| 20 | if(dp[j-coin]+ 1 < dp[j]){ |
| 21 | dp[j] = dp[j-coin]+ 1 |
| 22 | selected[j] = {...selected[j-coin]} |
| 23 | selected[j][coin]++ |
| 24 | } |
| 25 | } |
| 26 | } |
| 27 | |
| 28 | return dp[number]===Infinity?-1:selected[number] |
| 29 | } |
| 30 | |
| 31 | |
| 32 | // limit可以限制硬币的数量，比如{5000:0,1000:4,}就是没有5000的，1000的有四个 |