18 "output_type": "execute_result"
23 "require 'awesome_print'"
36 "[1, 2, 5, 10, 20, 50, 100, 200]"
41 "output_type": "execute_result"
45 "ways = {[0, 0] => 1}\n",
46 "coins = [1,2,5,10,20,50,100,200]"
64 "output_type": "execute_result"
81 "[1, 2, 5, 10, 20, 50, 100]"
86 "output_type": "execute_result"
106 "execution_count": 5,
108 "output_type": "execute_result"
112 "def change_count(coins, ncoins, total)\n",
113 " puts(\"#{coins[0...ncoins]} coins finding #{total}\")\n",
116 " elsif total < 0\n",
118 " elsif ncoins < 0 && total > 0\n",
121 " change_count(coins, ncoins-1, total) + change_count(coins, ncoins, total-coins[ncoins]) \n",
128 "execution_count": 6,
135 "output_type": "stream",
137 "[1, 2, 5] coins finding 5\n",
138 "[1, 2] coins finding 5\n",
139 "[1] coins finding 5\n",
140 "[] coins finding 5\n",
141 "[1, 2, 5, 10, 20, 50, 100] coins finding 5\n",
142 "[] coins finding 4\n",
143 "[1, 2, 5, 10, 20, 50, 100] coins finding 4\n",
144 "[] coins finding 3\n",
145 "[1, 2, 5, 10, 20, 50, 100] coins finding 3\n",
146 "[] coins finding 2\n",
147 "[1, 2, 5, 10, 20, 50, 100] coins finding 2\n",
148 "[] coins finding 1\n",
149 "[1, 2, 5, 10, 20, 50, 100] coins finding 1\n",
150 "[] coins finding 0\n",
151 "[1] coins finding 3\n",
152 "[] coins finding 3\n",
153 "[1, 2, 5, 10, 20, 50, 100] coins finding 3\n",
154 "[] coins finding 2\n",
155 "[1, 2, 5, 10, 20, 50, 100] coins finding 2\n",
156 "[] coins finding 1\n",
157 "[1, 2, 5, 10, 20, 50, 100] coins finding 1\n",
158 "[] coins finding 0\n",
159 "[1] coins finding 1\n",
160 "[] coins finding 1\n",
161 "[1, 2, 5, 10, 20, 50, 100] coins finding 1\n",
162 "[] coins finding 0\n",
163 "[1] coins finding -1\n",
164 "[1, 2] coins finding 0\n",
165 "[1, 2, 5] coins finding -5\n"
174 "execution_count": 6,
176 "output_type": "execute_result"
180 "change_count(coins, 3, 5)"
185 "execution_count": 40,
196 "execution_count": 40,
198 "output_type": "execute_result"
202 "def change_count_dp(coins, total, debug: false)\n",
203 " ncoins = coins.length - 1\n",
205 " (0..total).each do |t|\n",
206 " (0..ncoins).each do |n|\n",
207 " ways[[n, t]] = 1\n",
211 " (1..total).each do |t|\n",
212 " (0..ncoins).each do |n|\n",
213 " # including this coin\n",
214 " if t >= coins[n]\n",
215 " including = ways[[n, t-coins[n]]]\n",
220 " # excluding this coin\n",
222 " excluding = ways[[n-1, t]]\n",
227 " puts \"n: #{n} (#{coins[n]}p), t: #{t}, inc: #{including}, exc: #{excluding}\" if debug\n",
228 " ways[[n, t]] = including + excluding\n",
232 " ways[[ncoins, total]]\n",
239 "execution_count": 41,
247 "[0, 1, 2, 3, 4, 5, 6, 7, 8]"
250 "execution_count": 41,
252 "output_type": "execute_result"
261 "execution_count": 45,
268 "output_type": "stream",
270 "n: 0 (1p), t: 1, inc: 1, exc: 0\n",
271 "n: 1 (2p), t: 1, inc: 0, exc: 1\n",
272 "n: 2 (5p), t: 1, inc: 0, exc: 1\n",
273 "n: 3 (10p), t: 1, inc: 0, exc: 1\n",
274 "n: 4 (20p), t: 1, inc: 0, exc: 1\n",
275 "n: 5 (50p), t: 1, inc: 0, exc: 1\n",
276 "n: 6 (100p), t: 1, inc: 0, exc: 1\n",
277 "n: 7 (200p), t: 1, inc: 0, exc: 1\n",
278 "n: 0 (1p), t: 2, inc: 1, exc: 0\n",
279 "n: 1 (2p), t: 2, inc: 1, exc: 1\n",
280 "n: 2 (5p), t: 2, inc: 0, exc: 2\n",
281 "n: 3 (10p), t: 2, inc: 0, exc: 2\n",
282 "n: 4 (20p), t: 2, inc: 0, exc: 2\n",
283 "n: 5 (50p), t: 2, inc: 0, exc: 2\n",
284 "n: 6 (100p), t: 2, inc: 0, exc: 2\n",
285 "n: 7 (200p), t: 2, inc: 0, exc: 2\n",
286 "n: 0 (1p), t: 3, inc: 1, exc: 0\n",
287 "n: 1 (2p), t: 3, inc: 1, exc: 1\n",
288 "n: 2 (5p), t: 3, inc: 0, exc: 2\n",
289 "n: 3 (10p), t: 3, inc: 0, exc: 2\n",
290 "n: 4 (20p), t: 3, inc: 0, exc: 2\n",
291 "n: 5 (50p), t: 3, inc: 0, exc: 2\n",
292 "n: 6 (100p), t: 3, inc: 0, exc: 2\n",
293 "n: 7 (200p), t: 3, inc: 0, exc: 2\n",
294 "n: 0 (1p), t: 4, inc: 1, exc: 0\n",
295 "n: 1 (2p), t: 4, inc: 2, exc: 1\n",
296 "n: 2 (5p), t: 4, inc: 0, exc: 3\n",
297 "n: 3 (10p), t: 4, inc: 0, exc: 3\n",
298 "n: 4 (20p), t: 4, inc: 0, exc: 3\n",
299 "n: 5 (50p), t: 4, inc: 0, exc: 3\n",
300 "n: 6 (100p), t: 4, inc: 0, exc: 3\n",
301 "n: 7 (200p), t: 4, inc: 0, exc: 3\n",
302 "n: 0 (1p), t: 5, inc: 1, exc: 0\n",
303 "n: 1 (2p), t: 5, inc: 2, exc: 1\n",
304 "n: 2 (5p), t: 5, inc: 1, exc: 3\n",
305 "n: 3 (10p), t: 5, inc: 0, exc: 4\n",
306 "n: 4 (20p), t: 5, inc: 0, exc: 4\n",
307 "n: 5 (50p), t: 5, inc: 0, exc: 4\n",
308 "n: 6 (100p), t: 5, inc: 0, exc: 4\n",
309 "n: 7 (200p), t: 5, inc: 0, exc: 4\n"
318 "execution_count": 45,
320 "output_type": "execute_result"
324 "change_count_dp(coins, 5, debug: true)"
329 "execution_count": 43,
340 "execution_count": 43,
342 "output_type": "execute_result"
346 "change_count_dp(coins, 200)"
351 "execution_count": null,
361 "display_name": "Ruby 2.4.0",
366 "file_extension": ".rb",
367 "mimetype": "application/x-ruby",