Leetcode 322: Coin Change - Find minimum number of coins

Dec. 14, 2016

Julia likes to choose most popular post in code review on stackexchange.com, study the post, write down some notes, and also practice to write her own answer. Try to get into the community as active learner, teacher, and hardworking helper.

Her first post to answer question - no response so far, Dec. 14, 2016 8:19pm
http://codereview.stackexchange.com/a/149598/123986

She likes to write a second one:

Problem: 14 votes, 6 answers, 11K views
http://codereview.stackexchange.com/questions/47397/find-minimum-number-of-coins?rq=1

Same problem:
Leetcode:  Coin Change

http://www.cnblogs.com/grandyang/p/5138186.html

http://blog.csdn.net/liyuefeilong/article/details/50687271

Best solution - using DP, bottom up - Temple Ph.D.
https://github.com/jianminchen/LeetCode-Java-Solutions/blob/master/322.coin-change.java

This may be the best solution - written by MSFT employee, ICPC coach - PH.D.
Time complexity:
Space complexity:
https://github.com/jianminchen/LeetCode-17/blob/master/322_v1.cpp

Post the answer on the code review here. Julia, work on reputation target: 50, right now, 45. Once Julia has 50 reputation, she can leave a comment in any post.

Or click the link:
http://codereview.stackexchange.com/a/150130/123986

Leetcode 322: Coin Change

February 8, 2016

Julia likes to build a good fun memory about dynamic programming design, coding experience. Let this one - coin change build up good memory about Dynamic Programming. 


322 Coin change
http://www.cnblogs.com/grandyang/p/5138186.html

这道题只让我们求出最小的那种，对于求极值问题，我们还是主要考虑动态规划Dynamic Programming来做，我们维护一个一维动态数组dp，其中dp[i]表示钱数为i时的最小硬币数的找零，递推式为：

dp[i] = min(dp[i], dp[i - coins[j]] + 1);

其中coins[j]为第j个硬币，而i - coins[j]为钱数i减去其中一个硬币的值，剩余的钱数在dp数组中找到值，然后加1和当前dp数组中的值做比较，取较小的那个更新dp数组

To be continued.