{"id":298,"date":"2020-12-21T18:44:25","date_gmt":"2020-12-21T18:44:25","guid":{"rendered":"https:\/\/www.canosielabs.com\/blog\/?p=298"},"modified":"2020-12-21T18:44:25","modified_gmt":"2020-12-21T18:44:25","slug":"coin-change","status":"publish","type":"post","link":"https:\/\/www.canosielabs.com\/blog\/coin-change\/","title":{"rendered":"Coin Change"},"content":{"rendered":"\n

Today, we’ll analyze the popular interview question coin change<\/a>.<\/p>\n\n\n\n

You are given coins of different denominations and a total amount of money\u00a0amount<\/em>. Write a function to compute the fewest 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\u00a0-1<\/code><\/strong><\/p>\n\n\n\n

We have a infinite number of coins and only need to return the number of coins and not the coins themselves. As usual, let’s denote f(n) be the fewest number of coins required to add up to n.<\/p>\n\n\n\n

Optimal Substructure<\/strong><\/strong>\u00a0\u2013 The fewest number of coins to achieve a sum of n is the most optimal way of to achieve n from a value of n-i<\/strong> where i<\/strong> is one of the coins<\/strong>. In other words, given coins = [1, 2, 5], the most optimal way of achieving f(11):<\/p>\n\n\n\n

\"\"<\/figure><\/div>\n\n\n\n

Overlapping Sub-problem<\/strong> – Yes, given the optimal substructure described above, we do have overlapping subproblems. The function call tree clearly shows the number of duplicate calls invoked.<\/p>\n\n\n\n

\"\"<\/figure><\/div>\n\n\n\n

Base Case <\/strong>– The base case is when n=0, f(0)=0.<\/p>\n\n\n\n

DP Table<\/h2>\n\n\n\n

The DP table simply keeps track of the fewest number of coins f(n) in order to reach the sum n. I.e. memo[n] = f(n)<\/p>\n\n\n\n

Tabulation<\/h2>\n\n\n\n
public int coinChange(int[] coins, int amount) {\n\t\tif (amount < 0) {\n\t\t\treturn -1;\n\t\t} else if (amount == 0) {\n\t\t\treturn 0;\n\t\t}\n\n\t\tint[] memo = new int[amount + 1];\n\t\tmemo[0] = 0;\n\n\t\t\/\/ loop from 0 to amount to fill the array\n\t\tfor (int i = 1; i <= amount; i++) {\n\t\t\tint minFound = -1;\n \n\t\t\t\/\/ loop though all the coins and find the most optimum way of \n\t\t\t\/\/ getting to f(n) using the coins in the coin list \n\t\t\tfor (int j = 0; j < coins.length; j++) {\n\t\t\t    int memoIndex = i - coins[j];\n\t\t\t    \n\t\t\t    if (memoIndex >= 0) {\n\t\t\t\t\tint m = memo[memoIndex];\n\t\t\t\t\tif ((m > -1 && m < minFound) || minFound == -1) {\n\t\t\t\t\t\tminFound = m;\n\t\t\t\t\t}\n\t\t\t\t}\n\t\t\t}\n\n\t\t\tif (minFound >= 0) {\n\t\t\t\tmemo[i] = minFound + 1;\n\t\t\t} else {\n\t\t\t\tmemo[i] = -1;\n\t\t\t}\n\t\t}\n\t\treturn memo[amount];\n\t}<\/code><\/pre>

\n\n\n\n
Conclusion<\/h2>\n\n\n\n
We’ll omit the recursive DP solution since the problem is relatively straight forward.<\/p>\n","protected":false},"excerpt":{"rendered":"
Today, we’ll analyze the popular interview question coin change. You are given coins of different denominations and a total amount of money\u00a0amount. Write a function…<\/p>\n","protected":false},"author":3,"featured_media":255,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"bgseo_title":"","bgseo_description":"","bgseo_robots_index":"index","bgseo_robots_follow":"follow","footnotes":""},"categories":[11],"tags":[10],"class_list":["post-298","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-interview-coding-questions","tag-coding-questions"],"_links":{"self":[{"href":"https:\/\/www.canosielabs.com\/blog\/wp-json\/wp\/v2\/posts\/298","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.canosielabs.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.canosielabs.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.canosielabs.com\/blog\/wp-json\/wp\/v2\/users\/3"}],"replies":[{"embeddable":true,"href":"https:\/\/www.canosielabs.com\/blog\/wp-json\/wp\/v2\/comments?post=298"}],"version-history":[{"count":9,"href":"https:\/\/www.canosielabs.com\/blog\/wp-json\/wp\/v2\/posts\/298\/revisions"}],"predecessor-version":[{"id":311,"href":"https:\/\/www.canosielabs.com\/blog\/wp-json\/wp\/v2\/posts\/298\/revisions\/311"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/www.canosielabs.com\/blog\/wp-json\/wp\/v2\/media\/255"}],"wp:attachment":[{"href":"https:\/\/www.canosielabs.com\/blog\/wp-json\/wp\/v2\/media?parent=298"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.canosielabs.com\/blog\/wp-json\/wp\/v2\/categories?post=298"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.canosielabs.com\/blog\/wp-json\/wp\/v2\/tags?post=298"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}