## Friday, March 16, 2012

### a classical problem: coin change

Given a value in money N, and we want to change N into coins extracted from a set S={S1, ... Sm} of different coin values. How many diffferent ways to do we have to make the change. Assume that there are infinite coins of type Si.

Solution:

Define C(S, N, M) the way of changing the N given the M coins in S and compute the recursive solution
{"ft_lang_label":"__label__en","ft_lang_prob":0.8776572,"math_prob":0.8031018,"size":370,"snap":"2021-21-2021-25","text_gpt3_token_len":91,"char_repetition_ratio":0.12295082,"word_repetition_ratio":0.0,"special_character_ratio":0.24324325,"punctuation_ratio":0.13953489,"nsfw_num_words":0,"has_unicode_error":false,"math_prob_llama3":0.98305684,"pos_list":[0],"im_url_duplicate_count":[null],"WARC_HEADER":"{\"WARC-Type\":\"response\",\"WARC-Date\":\"2021-06-23T02:16:22Z\",\"WARC-Record-ID\":\"<urn:uuid:39246899-1be5-4f48-98e3-14bf48748b79>\",\"Content-Length\":\"125374\",\"Content-Type\":\"application/http; msgtype=response\",\"WARC-Warcinfo-ID\":\"<urn:uuid:856bbaa7-58e1-429c-a2ac-5c7db7776418>\",\"WARC-Concurrent-To\":\"<urn:uuid:d4f85082-b39c-4093-ac14-7ef3e2edff38>\",\"WARC-IP-Address\":\"142.250.81.193\",\"WARC-Target-URI\":\"https://codingplayground.blogspot.com/2012/03/classical-problem-coin-change.html\",\"WARC-Payload-Digest\":\"sha1:UCDAVOU7X7I3HJW4M25ZVCSLV43WK4JF\",\"WARC-Block-Digest\":\"sha1:GSSFXJSU3GUARJNWYXFPL33A2SQC3JKS\",\"WARC-Identified-Payload-Type\":\"application/xhtml+xml\",\"warc_filename\":\"/cc_download/warc_2021/CC-MAIN-2021-25/CC-MAIN-2021-25_segments_1623488528979.69_warc_CC-MAIN-20210623011557-20210623041557-00294.warc.gz\"}"}